HeadTest1 | Python Fiddle

'''
 Определим функцию P(n,k) следующим образом: P(n,k) = 1, если n может быть представлено в виде суммы k простых чисел (простые числа в записи могут повторяться, 1 не является простым числом) и P(n,k) = 0 в обратном случае.
 К примеру, P(10,2) = 1, т.к. 10 может быть представлено в виде суммы 3 + 7 или 5 + 5, а P(11,2) = 0, так как никакие два простых числа не могут дать в сумме 11.
 Определим функцию S(n) как сумму значений функции P(i,k) для всех i и k, таких что 1≤i≤n, 1≤k≤n. Таким образом, S(2) = P(1,1) + P(2,1) + P(1,2) + P(2,2) = 1, S(10) = 20, S(1000) = 248838.
 Найдите S(16572).
print("python")'''

'''Функция, которая составляет массив простых чисел,
идущих до указанного главной функции (задаётся, как n)
Этот массив создаётся успешно, но не очень то быстро, если скармливать
ему большие числа
К примеру, если у нас P(11,3), то на выходе этой функции будет массив [2, 3, 5, 7, 11]'''
def simple_list(n):
    simple_list=[]
    for num in range(2, int(n)+1):
        for elem in simple_list:
            if num % elem == 0:
                break
        else:
            simple_list.append(num)
    return simple_list

'''Эта функция берёт получившийся массив из предыдущей функции simple_list и в зависимости
от количества простых чисел (которые мы указываем, как k), из которых должна состоять сумма, расширяет этот массив
К примеру, если у нас P(11,3), то на выходе будет массив: [2, 2, 2, 3, 3, 3, 5, 5, 5, 7, 7, 7, 11, 11, 11], т.к. k=3
Оно нужно для того, что числа могут повторяться, т.е. вдруг 2+2+2 будет равно 11 и тогда дальше уже проверять особо смысла нет)'''
def sum_list(n,k):
    sum_list=[]
    lst=simple_list(n)
    i=0
    while i<len(lst):
        for count in range(k):
            sum_list.append(lst[i])
        i+=1
    return(sum_list)

'''Ну а это - главная функция, она берёт массив из sum_list и, грубо говоря, последовательно делает выборку из k элементов по всему массиву
и проверяет сумму в этой выборке. Если сумма соответствует исходному числу n - то выдаёт 1, если нет, то 0. Вот эту часть я сейчас насилую
т.к. в командной строке алгоритм вроде работает, а в таком виде, выдаёт что-то странное'''
def P(n,k):
    lst = sum_list(n,k)
    print(lst)
    i=0
    j=k
    while i<len(lst):
        check_list=lst[i:j] #[i:j] - это как раз пресловутая выборка, т.е. если у нас массив x=[1,2,3,4], то x[0:2]=[1,2]
        summ=sum(check_list)
        print(summ)
        if len(check_list) < k:
            break
        if summ > n:
            break
            return 0
        if summ == n:
            break
            return 1
        if summ < n:
            i+=1
            j+=1

Python Fiddle

Python Cloud IDE