Why does the program display the result for a very long time? Any error can eat?

The sum of primes less than 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all primes less than two million.

from math import * def PrimeNumber (n): if n == 1: return False if n == 2: return True limit = sqrt (n) div = 2 while div <= limit: # По формуле, достаточно перебрать делители числа до квадратного корня самого числа if n % div == 0: return False div += 1 return True s = 2 a = 3 while a < 2000000: if PrimeNumber (a): s += a else: a += 2 print (s) 
  • one
    Because to determine the simplicity of a number, you use factorization, and the problem of factorization is highly complex. I think, for your task more suitable Sieve Eratosthenes . Or you can try to use probabilistic algorithms for determining the simplicity (Fermat, Nightingale-Strassen, Luke, Miller-Rabin tests), but they will return the correct answer to you with a certain probability (not 100%). - Mikhail Murugov
  • one
  • In this case, with the sieve a more correct approach - it will give all the prime numbers at once, and the definition of simplicity is more beneficial for the test of a single number or a small range - MBo
  • algorithm for finding all primes up to some integer n, in this case the number n is the sequence number? - PythonLoveMe
  • n is the limit. In your case, n = 2*10**6 . - Mikhail Murugov

4 answers 4

You can use the sieve of Eratosthenes to search for primes, the function is taken from the answer in English StackOverflow

 # Функция, реализующая решето Эратосфена def iprimes_upto(limit): is_prime = [True] * limit for n in range(2, limit): if is_prime[n]: yield n for i in range(n*n, limit, n): # start at ``n`` squared is_prime[i] = False # Получаем все простые числа до 2 миллионов primes = list(iprimes_upto(2000000)) print(sum(primes)) # выводим сумму > 142913828922 
  • it would be nice to indicate the author ... ;-) - MaxU 1:02 pm
  • one
    @MaxU, to be honest, I didn’t remember exactly where the code took it :) I just found it on my computer in my examples. Thank you, clarified a bit the answer - Alexshev92

We take a function that returns prime numbers through the Sieve of Eratosthenes, and summarize them:

 def primes(n): """ Returns a list of primes < n """ sieve = [True] * n for i in range(3,int(n**0.5)+1,2): if sieve[i]: sieve[i*i::2*i]=[False]*((ni*i-1)//(2*i)+1) return [2] + [i for i in range(3,n,2) if sieve[i]] print(sum(primes(2_000_000))) # 142913828922 

UPD. @MaxU suggested using an optimized version of the prime number function: https://stackoverflow.com/a/3035188/5909792 . It looks difficult, but in comparison with the previous one, it produced the result 16 times faster on my machine.

  • your implementation can be accelerated by at least an order of magnitude if: 1. immediately exclude all even numbers for i in range(3,int(n**0.5)+1,2) . 2) when in the cycle of a prime number, delete all multiples of a given prime number using slices ( an example is the function primes() ) ;-) - MaxU
  • one
    @MaxU, Adishche, not a function: D - gil9red 1:46 pm
  • yeah, added it as an answer, but with debug / additional information to make it clearer how it works ... - MaxU

Here is a very effective implementation of the Eratosthenes sieve (c) Robert William Hanks - I just added debug information:

 def primes(n): """ Returns a list of primes < n """ # (c) Robert William Hanks - https://stackoverflow.com/a/3035188/5741205 sieve = [True] * n print("все чётные числа игнорируются и будут пропущены при возврате...\n") for i in range(3,int(n**0.5)+1,2): if sieve[i]: print('содержимое решета:\t{}'.format([x for x in range(3,n,2) if sieve[x]])) print(f'i:{i} вычёркиваем все числа кратные "{i}", начиная с "{i}^2": {list(range(i*i, n, 2*i))}') sieve[i*i::2*i]=[False]*((ni*i-1)//(2*i)+1) print(f'sieve[{i}*{i}::2*{i}]=[False]*(({ni}*{i-1})//(2*{i})+1)') print('содержимое решета:\t{}'.format([x for x in range(3,n,2) if sieve[x]])) print('*' * 60) return [2] + [i for i in range(3,n,2) if sieve[i]] 

Output for n=50 :

 In [165]: primes(50) все чётные числа игнорируются и будут пропущены при возврате... содержимое решета: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49] i:3 вычёркиваем все числа кратные "3", начиная с "3^2": [9, 15, 21, 27, 33, 39, 45] sieve[3*3::2*3]=[False]*((47*2)//(2*3)+1) содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49] ************************************************************ содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49] i:5 вычёркиваем все числа кратные "5", начиная с "5^2": [25, 35, 45] sieve[5*5::2*5]=[False]*((45*4)//(2*5)+1) содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49] ************************************************************ содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49] i:7 вычёркиваем все числа кратные "7", начиная с "7^2": [49] sieve[7*7::2*7]=[False]*((43*6)//(2*7)+1) содержимое решета: [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] ************************************************************ Out[165]: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 
     n = int(input()) numbers = [] s = 0 for i in range (n + 1): #Заполняем массив элентами от 0 до n numbers.append (i) numbers[1] = 0 #Так как второй элемент массива это единица, а она не является ни простым, ни составным i = 2 #В данном случае это индекс, то есть мы начинаем с 3 элемента, на месте которого стоит 2 while i <= n: if numbers[i] != 0: j = 2*i while j <= n: numbers[j] = 0 j += i i += 1 numbers = set(numbers) #Избавляемся от повторяющихся нулей , но один останется numbers.remove (0) #Теперь нулей нету print (sum(numbers))