Algorithm for Finding Primes

Optimization of the algorithm for finding prime numbers

2 3 5 7 11 13 17 19 23 29 31 ... $ 250.000 ...

It was a long time ago, at the university, when we began to study the Pascal programming language and the homework was to create an algorithm for finding prime numbers.

The algorithm was invented and then implemented in the target language. The program requested the user number N and searched for all prime numbers up to N inclusive. After the first successful test, an overwhelming desire immediately arose to introduce N = “many”. The program worked, but not as fast as we would like. Naturally, the case was in numerous checks (of the order of N * N / 2), so I had to get rid of the extra. The result was 5 similar algorithms, each of which worked faster than the previous one. Recently I wanted to remember and implement them, but this time in Python.

So let's go. The first algorithm that hit the student head is shown in Listing 1.

#  1 #  N n = input("n=") #        lst = [] #  k     k = 0 #     2  N for i in xrange(2, n+1): #     2   for j in xrange(2, i): #    if i % j == 0: k = k + 1 #   ,     if k == 0: lst.append(i) else: k = 0 #     print lst 

You very quickly realize that there is no need to count the divisors of each number, and therefore the variable k can be released from its duties. Indeed, if at least one divider exists, then the number is no longer simple. See Listing 2.

 #  2 n = input("n=") lst = [] for i in xrange(2, n+1): for j in xrange(2, i): if i % j == 0: #   ,   . break else: lst.append(i) print lst 

The break construction allows us to complete the execution of the inner loop and move on to the next iteration of the outer one.
Then the question arises: “why divide by 4, if the number is not divided by 2?”. We come to the conclusion that it is necessary to look for divisors only among prime numbers not exceeding the dividend. Our algorithm turns into ... see Listing 3.

 #  3 n = input("n=") lst=[] for i in xrange(2, n+1): #    (lst)   for j in lst: if i % j == 0: break else: lst.append(i) print lst 

And then we recall the theory of numbers and we understand that we need to go through only numbers that do not exceed the root of the desired one. For example, if the number M has a divisor pi, then there is a divisor qi such that pi * qi = M. That is, to find a pair, it suffices to find a smaller one. Among all the pairs, the estimated pair with the lowest maximum is a pair with equal pi and qi, that is, pi * pi = M => pi = sqrt (M). See Listing 4.

 #  4 from math import sqrt n = input("n=") lst=[] for i in xrange(2, n+1): for j in lst: if j > int((sqrt(i)) + 1): lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst 

The code in Listing 4, with N = 10,000, runs about 1000 times faster than the very first option. There is one more “accelerator”, to check only those numbers that end in 1, 3, 7 or 9 (since the others are obviously divided into 2 or 5). Observe Listing 5.

 #  5 from math import sqrt n = input("n=") lst=[] for i in xrange(2, n+1): if (i > 10): if (i%2==0) or (i%10==5): continue for j in lst: if j > int((sqrt(i)) + 1): lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst 

Due to a minor change in Listing 5, we get a slight increase in speed:

 #  6 from math import sqrt n = input("n=") lst=[2] for i in xrange(3, n+1, 2): if (i > 10) and (i%10==5): continue for j in lst: if j > int((sqrt(i)) + 1): lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst 

Total: The program from the last listing runs about 1300 times faster than the original version.
I did not set myself the task of writing a program as quickly as possible to solve this problem, it is rather a demonstration to novice programmers that a correctly composed algorithm plays a significant role in optimizing your programs.
')
PS
Thanks to the comments we get Listing 7:

 #  7 n = input("n=") lst=[2] for i in xrange(3, n+1, 2): if (i > 10) and (i%10==5): continue for j in lst: if j*j-1 > i: lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst 

when N = 10,000, lecture time:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053

Sieve of Eratosthenes:

 #  8 n = input("n=") a = range(n+1) a[1] = 0 lst = [] i = 2 while i <= n: if a[i] != 0: lst.append(a[i]) for j in xrange(i, n+1, i): a[j] = 0 i += 1 print lst 

Results with n = 1,000,000:
time 7 = 7.088
time 8 = 1.143