python sum of primes

Question

Я связываюсь, чтобы сделать программу python, которая будет генерировать сумму простых чисел для числа, но программа не дает правильный результат, пожалуйста, скажите мне, почему.

b=1 
#generates a list of numbers. 
while b<100: 
    b=b+1 
    x = 0.0 
    a = 0 
    d = 0 
    #generates a list of numbers less than b. 
    while x<b: 
     x=x+1 
     #this will check for divisors. 
     if (b/x)-int(b/x) == 0.0: 
      a=a+1 
     if a==2: 
      #if it finds a prime it will add it. 
      d=d+b 
print d 

Я сделал это, чтобы сгенерировать список простых чисел успешно, но я не мог получить простые числа, чтобы добавить.

Это код, который я использовал для создания списка простых чисел.

b=1 
while b<1000: 
    b=b+1 
    n = b 
    x = 0.0 
    a = 0 
    while x<n: 
     x=x+1 
     if (n/x)-int(n/x) == 0.0: 
      a=a+1 
    if a==2: 
     print b 

Answer 1

Ваш d переменная сбрасывается во время каждой итерации вашего внешнего контура , Переместите инициализацию из этого цикла.

Кроме того, проверка a == 2 должна происходить только один раз за итерацию внешнего контура. Переместите его из внутреннего контура.

b=1 
d = 0 
#generates a list of numbers. 
while b<100: 
    b=b+1 
    x = 0.0 
    a = 0 
    #generates a list of numbers less than b. 
    while x<b: 
     x=x+1 
     #this will check for divisors. 
     if (b/x)-int(b/x) == 0.0: 
      a=a+1 
    if a==2: 
     #if it finds a prime it will add it. 
     d=d+b 
print d 

Результат:

1060 

В то время как мы на это, давайте попробуем очистки кода, так что это более понятным. Вы можете перемещать внутренний контур в свою собственную функцию, чтобы читатели могли более четко понять свою цель:

def is_prime(b): 
    x = 0.0 
    a = 0 
    while x<b: 
     x=x+1 
     #this will check for divisors. 
     if (b/x)-int(b/x) == 0.0: 
      a=a+1 
    if a==2: 
     return True 
    else: 
     return False 

b=1 
d=0 
#generates a list of numbers. 
while b<100: 
    b=b+1 
    if is_prime(b): 
     d=d+b 
print d 

Это также полезно использовать имена переменных, которые описывают то, что они представляют собой:

def is_prime(number): 
    candidate_factor = 0 
    amount_of_factors = 0 
    while candidate_factor<number: 
     #A += B is equivalent to A = A + B 
     candidate_factor += 1 
     #A little easier way of testing whether one number divides another evenly 
     if number % candidate_factor == 0: 
      amount_of_factors += 1 
    if amount_of_factors == 2: 
     return True 
    else: 
     return False 

number=1 
prime_total=0 
#generates a list of numbers. 
while number<100: 
    number += 1 
    if is_prime(number): 
     prime_total += number 
print prime_total 

for петля более idomatic чем while петли, что приращение счетчика:

def is_prime(number): 
    amount_of_factors = 0 
    for candidate_factor in range(1, number+1): 
     if number % candidate_factor == 0: 
      amount_of_factors += 1 
    if amount_of_factors == 2: 
     return True 
    else: 
     return False 

prime_total=0 
#generates a list of numbers. 
for number in range(2, 101): 
    if is_prime(number): 
     prime_total += number 
print prime_total 

Если вы чувствуете себя смелым, вы можете использовать список всесторонни чтобы сократить количество используемых вами петель:

def is_prime(number): 
    factors = [candidate_factor for candidate_factor in range(1, number+1) if number % candidate_factor == 0] 
    return len(factors) == 2 

#generates a list of numbers. 
primes = [number for number in range(2, 101) if is_prime(number)] 
prime_total = sum(primes) 
print prime_total 

Answer 2

Просто просуммировать список с помощью кода вы использовали для создания списка:

d = sum(d) 
print d 

Answer 3

, если вы делаете это ради обучения питона есть более сжатый (>> меньше error- склонными) способами этого. Из Вашего вопроса Я предполагаю, что вы пытаетесь суммировать все простые числа ниже, и в том числе 100:

sum=0 
limit=100 
for n in range(2,limit+1): 
    if all(n % i for i in range(2, n)): 
    sum += n 
print sum 

гравюр 1060

Answer 4

Сводные описания являются мощным инструментом в Python. Думайте о них как о петле в стероидах. :-) Вы можете использовать их для реализации пробного деления, что является простым способом поиска простых чисел.

Это работает так:

In [4]: sum(prime_list(100)) 
Out[4]: 1061 

В prime_list функции:

def prime_list(num): 
    """Returns a list of all prime numbers up to and including num. 
    Based on trial division. 

    :num: highest number to test 
    :returns: a list of primes up to num 

    """ 
    if num < 3: 
     raise ValueError('this function only accepts arguments > 2') 
    candidates = range(3, num+1, 2) # (a) 
    L = [c for c in candidates if all(c % p != 0 for p in range(3, c, 2))] #(b) 
    return [1, 2] + L 

Теперь для объяснения. За исключением 2, все простые числа нечетны.Таким образом, все нечетные числа от 3 до num (100 в этом случае) являются кандидатами на простые числа. Давайте создать список тех, кто, как это сделано в (а):

In [5]: num = 100 

In [6]: range(3, num+1, 2) 
Out[6]: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99] 

Для нечетного числа c быть простым, необходимо обеспечить, чтобы c по модулю всех предыдущих нечетных чисел p должен быть отличен от нуля. Скажем c является 25.

In [7]: c = 25 

Тогда p в:

In [8]: range(3, c, 2) 
Out[8]: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23] 

Теперь проверьте c по модулю p:

In [9]: [c % p != 0 for p in range(3, c, 2)] 
Out[9]: [True, False, True, True, True, True, True, True, True, True, True] 

Как мы знаем, 25% 5 == 0, поэтому второй элемент в списке - False. Однако для числа, которое должно быть простым, все элементы в списке должны быть правдой:

In [10]: all(c % p != 0 for p in range(3, c, 2)) 
Out[10]: False 

Таким образом, 25 не является простым.

Давайте попробуем еще раз для c 41:

In [11]: c = 41 

In [12]: range(3, c, 2) 
Out[12]: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39] 

In [13]: [c % p != 0 for p in range(3, c, 2)] 
Out[13]: [True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True] 

In [14]: all(c % p != 0 for p in range(3, c, 2)) 
Out[14]: True 

И в самом деле 41 является простым.

Так prime_list возвращает список простых чисел:

In [15]: prime_list(100) 
Out[15]: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 

Обобщая, что выше мы просто используем sum() функцию:

In [16]: sum(prime_list(100)) 
Out[16]: 1061 

Edit: На основе комментариев, я попробовал улучшение что WillNess предлагает и реальное сито с использованием комплектов:

def prime_list(num): 
    if num < 3: 
     raise ValueError('this function only accepts arguments > 2') 
    candidates = range(3, num+1, 2) 
    L = [c for c in candidates if all(c % p != 0 for p in range(3, c, 2))] 
    return [1, 2] + L 

def prime_list2(num): 
    if num < 3: 
     raise ValueError('this function only accepts arguments > 2') 
    candidates = range(3, num+1, 2) 
    L = [c for c in candidates if all(c % p != 0 for p in 
     range(3, int(math.sqrt(c))+1, 2))] 
    return [1, 2] + L 

def prime_list3(num): 
    candidates = set(range(3, num+1, 2)) 
    results = [1, 2] 
    while candidates: 
     t = list(candidates)[0] 
     results.append(t) 
     candidates -= set(range(t, num+1, t)) 
    return results 

Некоторые тайминги для num=100:

In [8]: %timeit prime_list(100) 
1000 loops, best of 3: 180 us per loop 

In [9]: %timeit prime_list2(100) 
1000 loops, best of 3: 192 us per loop 

In [10]: %timeit prime_list3(100) 
10000 loops, best of 3: 83.9 us per loop 

И num=1000:

In [11]: %timeit prime_list(1000) 
100 loops, best of 3: 8.05 ms per loop 

In [12]: %timeit prime_list2(1000) 
100 loops, best of 3: 2.43 ms per loop 

In [13]: %timeit prime_list3(1000) 
1000 loops, best of 3: 1.26 ms per loop 

num = 5000:

In [14]: %timeit prime_list(5000) 
1 loops, best of 3: 166 ms per loop 

In [15]: %timeit prime_list2(5000) 
100 loops, best of 3: 11.1 ms per loop 

In [16]: %timeit prime_list3(5000) 
100 loops, best of 3: 15.3 ms per loop 

И наконец num=50000:

In [18]: %timeit prime_list3(50000) 
1 loops, best of 3: 1.49 s per loop 

In [19]: %timeit prime_list2(50000) 
1 loops, best of 3: 170 ms per loop 

Answer 5

Кевин правильно ответил на заданный вами вопрос. Позвольте мне ответить на ваш вопрос: не спросить, но должен иметь: Каков наилучший способ вычислить сумму простых чисел менее n. Ответ заключается в использовании сита:

def sumPrimes(n): 
    sum = 0 
    sieve = [True] * (n+1) 
    for p in range(2, n): 
     if sieve[p]: 
      sum += p 
      for i in range(p*p, n, p): 
       sieve[i] = False 
    return sum 

Этот код реализует Решето Эратосфена, суммируя простые числа, как она идет.Он работает по несколько раз выбирая наименьшее перекрещивания номер (р в приведенном выше коде, который выбирается, когда sieve[p] является True), затем вычеркивать все его кратные (я в приведенном выше коде, который увеличивается на р для вычисления кратных значений p), начиная с его площади (поскольку все меньшие композиты уже вычеркнуты). Пример использования функции print sumPrimes(100), который печатает 1060, что является правильным ответом.

Обратите внимание, что ответ Роланда не выполняет Сито Эратосфена, хотя он утверждает, что он это делает; использование модульной функции - это подделка, на которую ответ Роланда использует пробное деление, не Сито Эратосфена.

Если вы заинтересованы в программировании с помощью простых чисел, я скромно рекомендую этот essay в моем блоге.

Answer 6

def sum_of_prime(num): 
     if num < 2: 
      return 'Please enter values greater than 2' 
     if num == 2: 
       return 2 
     sum = 0 
     for j in range(2,num): 
       for i in range(2,j): 
         if (j % i) == 0: 
           break 
       else: 
         print j 
         sum = sum + j 
     return sum 
num = int(raw_input()) 
result = sum_of_prime(num) 
print result