Generate Prime Numbers with Python

Hello everyone. I am Ahmad, a noobie here.
Today I'm gonna share a bit of my Python coding experience.
As of you or any other programmer did, i too learned to solve prime number with coding in my early months of learning programming.

In my case I used Python which has easy-to-understand syntax, compared like to my first coding language C++ which at that time I only understand a bit about it.

Back to the topic, my first prime solving program is to print the result whether an integer input is prime number or not.

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. (Wikipedia)

def isPrime(N):
    for x in range(2,N):    #numbers from 2 to N-1
        if N%x == 0:
            return False
    return True

isPrime(17)      #output: True
isPrime(9)       #output: False    

Then, using the function above as a base I was going deeper with making new function that print out all prime numbers below an integer input.

def printPrimes(M):
    for x in range(2,M):
        if isPrime(x):
            print(x, end=" ")

printPrimes(20)    #output: 2 3 5 7 11 13 17 19

#Later on, I found this one-liner online, pretty cool right
primeList= lambda M: [x for x in range(2,n) if all(x%k for k in range(2,x))]
primeList(20)      #output: [2, 3, 5, 7, 11, 13, 17, 19]

I guess you all had used the same algorithm in your first prime solving program. Back then, I never try to find out "Is a certain big number prime or not?" or "how many primes are there below a certain big number?". My curiosity just stop at number 100.

But recently, about a half year ago I found this article by Sadrach Pierre, Ph.D about memoization in fibonacci sequence. I learned first time about caching and its effect to speed and performance here. Also about there's a limit of interpreter can compute due to memory issue and timeout limit.

Yes, it's challenging to see how fast and efficient our code could run. And I started it by challenging Prime Numbers. Then I found this one.

def isPrime(N):
    for i in range(2,int(N**0.5)+1):   #numbers from 2 to square-root of N
        if N%i==0:
            return False
    return True

#It's similiar with the first isPrime function I learned, except the threshold factor being square-root of N.
#Iteration of computation is also decreased to about square-root of N. It means the function is faster.
#Though at that time I don't really know where this root-square came from.

And this one about prime number from adjacent of 6n. Aside from 2 and 3, all primes satisfy this pattern, whether being 6n+1 or 6n+1. But not all this adjacents are prime.
6x(1)+1 = 7 :prime
6x(1)-1 = 5 :prime
6x(4)+1 = 25 :not prime
6x(4)-1 = 23 :prime

A little explanation by example about square-root-of-N-Threshold, see example composite numbers in table below

20	16	27	36
1 x 20	1 x 16	1 x 27	1 x 36
2 x 10	2 x 8	3 x 9	2 x 24
4 x 5	4 x 4		3 x 12
			4 x 9
			6 x 6

As you can see above, when the left-number increase, the right-number decrease. The left-number never been greater than square-root of N.

Now we can narrow down the candidates of prime numbers from all numbers below M to odd numbers below M then to adjacent of 6n. See the comparison table( case example for M=50 ).

Prerequisites	members below 50	Quants	Annotation
all numbers (2 to M)	2,3,4,...,48,49	48	All in scope
odd numbers (2 to M)	3,5,7,...,47,49	24	2 not included
adjacent of 6n, for n start from 1	5,7,11,13,...,49	16	2,3 not included

With adjacent of 6n pattern, we can minimize the numbers of candidates to to a certain degree. Now it's time to transpire it into python code.

def isPrime(N):
    for i in range(2,int(N**0.5)+1):
        if N%i==0:
            return False
    return True

def primeGenerator(M):
    result= [2,3]
    maxn= M//6
    n=1
    while n<=maxn:
        a= 6*n - 1
        if isPrime(a):
            result.append(a)
        b= 6*n + 1
        if b>=M:
            break
        else:
            if isPrime(b): result.append(b)
        n+=1
    return result

Function above has two type of approach in speeding up. First approach is narrowing the dividing factor (to square-root of N) and second approach is narrowing the candidates (to adjacent of 6n). Next question, Can We make it even faster?

Ofcourse we can. This time we won't do improvement in second type of approach( cause I still have no idea ), instead we'll focus on first type of approach( narrowing the dividing factor ). See this table based on candidates from adjacent of 6n.

The highlighted items is composite numbers and its factors. Do you see the similiarity between them. Yess, the factor is came from prime as well. What does it mean? It means we can narrow it again, from all numbers below N to all numbers below square-root of N then finally to a set of primes.

Type	Prerequisities	members for N= 71	Quants
A	all numbers below N	2,3,4,...,70	69
B	all numbers below square-root of N	2,3,...,7,8	7
C	set of primes below square-root of N	2,3,5,7	4
D	Type C exclude 2,3	5,7	2

We're using type B in previous primeGenerator function, if we can apply type D above our app will boost, definetely. Well, it's a bit tricky to apply this, because we need dynamic array for caching set of primes as dividing factors.

def fastGenerator(M):
    result=[2,3]
    a=5
    b=7
    count=3
    factor=[5]       #caching factor
    threshold=25     #instead of calculating square-root on each candidate,
    while a<M:       #...I change threshold every other time
        if a==threshold:
            factor.append(result[count])
            threshold=factor[-1]**2
            count+=1
        elif all(a%k for k in factor):
            result.append(a)
        if b>=M:
            break
        elif b==threshold:
            factor.append(result[count])
            threshold=factor[-1]**2
            count+=1
        elif all(b%k for k in factor):
            result.append(b)
        a+=6
        b+=6
    return result

Here is a performance speed test using timeit function.

Name	Features	20K	100K	500K	1000K	2000K	5000K
primeList	Standard	2.59s	62.7s
primeListCache	Caching factor	0.34s	5.65s	115.3s
primeGenerator	Adjacent 6n candidates, Square-Root of M factor	0.03s	0.28s	2.38s	7.01s	17.23s	76.2s
fastGenerator	same as above plus caching			0.76s	1.88s	5.08s	18.83s

I stop testing the function if it passed 50s. I didn't include first two test-variable in fastGenerator because I guess it will be too small. I'll make sure I'll be more detailed in the future and not skipped even a tiny testing-variable.

Conclusion

We can speeding up our high-consumed memory computation by eleminating unnecessary computation. In above case we eliminate many iterations from two types of approach. From the numbers of candidates and from the numbers of dividing factor.

The important part of speeding up the app is you must understand very well about the topic of your app, then do some research to understand it even more. By doing that you will find flaws in your algorithm as well as the possibility of improvement.

Closure

After completing this challenge, I feel proud to my self. It proved that I'm capable, and I start wondering if it just me, or is it me the first one to find this method of generating primes from big number, Oh my God am I a genius? OFCOURSE NOT! WAKE UP BOY..!

Later on, I found many articles about primes and several methods of generating primes. The same method as I used in above function was published decades ago. But it still somewhat Satisfying, I mean like breaking out your own record.

See you in another post, feel free to comment. And I apologize in advance if any of my words offense you. It's my first blog post anyway. Thank You.