Question: find all prime numbers within 100

  This is a very basic and classic small code. It is very likely that we will traverse the filter in this way:

def find_odd(numb):
    flag = 0
    if numb ==2:
        return True
    else:
        for i in range(2,numb):
            flag = 0
            if numb%i == 0:
                return False
        flag = 1
    if flag == 1:
        return True
 
if __name__ == "__main__":
    my_list = []
    for i in range(2,101):
        if find_odd(i) ==True:
            my_list.append(i)
        else:
            continue
    print(my_list)

Fine, it has normally completed our set tasks, but now it needs to be faster? What if it's not within 100 but within a larger range?

Here we only need a little change to traverse from 2 toChange from 2 toThis will save a lot of time when dealing with its wide range.

def find_odd(numb):
    flag = 0
    if numb ==2:
        return True
    else:
        j = int(round(numb**0.5)+1)
        for i in range(2,j):
            flag = 0
            if numb%i == 0:
                return False
        flag = 1
    if flag == 1:
        return True
 
if __name__ == "__main__":
    my_list = []
    for i in range(2,101):
        if find_odd(i) ==True:
            my_list.append(i)
        else:
            continue
    print(my_list)

How about a little faster?

Well, here's a conclusion: any prime number greater than or equal to 5 must be distributed near the multiple of six

Note that the inverse proposition of this conclusion is not True

It can be understood simply as follows: 2 * 2 = 4, 2 * 3 = 6, 2 * 2 * 2 = 8, the integer multiples of 2 and 3 must not be prime numbers. On the whole integer axis covered by their integer multiples, there may be gaps near the multiples of 2 * 3

In other words, we don't have to filter so many numbers from 1 to numb to judge at a time. We just need to judge near the multiple of six

def find_odd(numb):
    flag = 0
    if numb ==2:
        return True
    else:
        j = int(round(numb**0.5)+1)
        for i in range(2,j):
            flag = 0
            if numb%i == 0:
                return False
        flag = 1
    if flag == 1:
        return True
 
if __name__ == "__main__":
    my_list = [2,3]
    for i in range(1,100//6+1):
        if find_odd(i*6-1) ==True:
            my_list.append(i*6-1)
        if find_odd(i*6+1)==True:
            my_list.append(i*6+1)
    print(my_list)

Under these two optimizations, the normal code is already very fast, but what if it needs to be faster???

Here we will introduce the famous algorithm Euler sieve

def EulerSieve(n):
            filter, primers = [False for _ in range(n + 1)], []
            for i in range(2, n + 1):
                if not filter[i]:
                    primers.append(i)
                for prime in primers:
                    if i * prime > n:
                        break
                    filter[i * prime] = True
                    if i % prime == 0:
                        break
            return primers
if __name__ =="__main__":
    mylist = EulerSieve(100)
    print(mylist)

First, assign all filter s to False as our "sieve" and regenerate it into an empty list of primers to store the results

The judgment logic is that if the element filter[i] is False, the element I (i.e. prime number) is added to the primers

Then multiply each element by the current cyclic quantity i in the primers, and change the corresponding multiplied index value in the filter to True (that is, it is filtered out), because the integer multiple of the prime number must be a non prime number. In this way, we reduce a lot of computation.

So let's check the code. Will it really be much faster?

import timeit
import matplotlib.pyplot as plt
def compare():
    E_time=[]
    N_time=[]
    Step=[]
    for step in range(1000,20001,2000):
        def EulerSieve(n=step):
            filter, primers = [False for _ in range(n + 1)], []
            for i in range(2, n + 1):
                if not filter[i]:
                    primers.append(i)
                for prime in primers:
                    if i * prime > n:
                        break
                    filter[i * prime] = True
                    if i % prime == 0:
                        break
            return primers

        def find_odd(numb):
            flag = 0
            if numb ==2:
                return True
            else:
                j = int(round(numb**0.5)+1)
                for i in range(2,j):
                    flag = 0
                    if numb%i == 0:
                        return False
                flag = 1
            if flag == 1:
                return True

        def Normal_find(n=step):
            mylist = []
            for i in range(2,n+1):
                if find_odd(i) == True:
                    mylist.append(i)
            return mylist
        E_time.append(round(timeit.timeit(EulerSieve, number=100),4))
        N_time.append(round(timeit.timeit(Normal_find, number=100),4))
        Step.append(step)
    return E_time,N_time,Step
if __name__ =="__main__":
    Y1_list,Y2_list,X_list=compare()
    plt.plot(X_list,Y1_list,color = 'red',label='EulerSieve Method')
    plt.plot(X_list,Y2_list,color='green',linewidth=1.0,linestyle='--',label='Normal Method')
    plt.ylabel('time consuming/s',fontproperties = 'SimHei',fontsize = 12)
    plt.xlabel('Maximum prime range/Hundred times',fontproperties = 'SimHei',fontsize = 12)
    plt.title('Comparison of prime number screening time between Euler sieve and conventional algorithm',fontproperties = 'SimHei',fontsize = 15)
    plt.show()

Just put the results

The green dotted line is the normal algorithm, and the red solid line is the Euler sieve algorithm, which is excellent with the naked eye