Сумма всех простых чисел меньше заданного рекурсивно

Question

нужно мне решить одну простую задачку, но додуматься не могу. Вот что написал сейчас:

def IsPrime(n):
    if n % 2 == 0:
        return n == 2
    d = 3
    while d * d <= n and n % d != 0:
        d += 2
    return d * d > n

def pi(x):
    sum = 0
    if x > 1:
        if IsPrime(x - 1):
            sum += pi(x-1)
            print (x)
            return x
        else:
            pi(x-1)
            return 0
    else:
        return sum

print(pi(10))

задача вывести сумму всех простых чисел меньше 10, для этого сделал функцию проверки и рекурсивную pi. Внутри вызываю с параметром на 1 меньше, но как посчитать саму сумму не пойму.

Answer 1

зачем так сложно то :)

def pi(x):
    return 2 if x == 2 else ((x if IsPrime(x) else 0) + pi(x - 1))

основные принципы:

выводим 2, если x равно 2, ну можно рекурсию и позже прервать - например выводить 0, если x равно 0
иначе если число простое - то прибавляем к результату функции с меньшим аргументом это число x иначе 0 (т.е. составные числа не учитываем)

P.S.

можно чуть-чуть упростить функцию:

def pi(x):
    return 2 if x == 2 else (x * int(IsPrime(x)) + pi(x - 1))

P.P.S.

а чтобы учесть все целые числа можно сделать так:

def pi(x):
    return 0 if x < 2 else (x * int(IsPrime(x)) + pi(x - 1))

Answer 2

А зачем вам рекурсия?

def pi(n):
    primes = [2]
    for i in range(3,n,2):
        is_prime = True
        for p in primes[:len(primes)//2]:
            if i % p == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(i)
    return sum(primes)

print(pi(10000)) # 5736396

Answer 3

def pi(x):
    sum = 0
    if x > 1:
        if IsPrime(x):
            sum += x
        return sum + pi(x - 1)
    else:
        return 0

БЛОГ НА HUSL

Сумма всех простых чисел меньше заданного рекурсивно

Ответы (3 шт):