Problem Description
We know that the first prime number is 2, the second prime number is 3, and the third prime number is 5...Can you calculate the 2020th prime number?
solution
When seeing this problem of finding prime numbers, many people think of the double loop brute force search for the first time. If you only find the first few prime numbers, you can use this brute force search method. But if you are looking for the 2020th prime number and the 9999th prime number, this violent method is not applicable.
At this time, you can use the sieve method to find prime numbers. This article introduces the Euler sieve method. The principle used is that multiples of prime numbers must not be prime numbers. Therefore, the multiples of prime numbers are directly marked as composite numbers to achieve the purpose of screening prime numbers.
There is also the Ezos sieve method with this same idea, but the Ezos sieve method has a defect: for a composite number, it may be sieved many times, for example, 20 = 210 = 45. To improve this, use the smallest prime factor of the composite number to screen to ensure that each composite number is only screened once. This is the Euler Sieve method.
But how to make each composite number be filtered only once, let's look at the following code.
Code:
| def ouLaShai(n): lis = [True for i in range(n + 1)] # Used to filter record composite number lis2 = [] # Store prime number for i in range(2, n + 1): if lis[i ]: # If it is not filtered, add it to Lis2 lis2.append(i) for prime in lis2: if i * prime> n: # Ensure that it is less than n and cannot exceed the range break lis[i * prime] = False # Record the composite number if i% prime == 0: # The key step is to ensure that each composite number is filtered only once break return lis2 |
|---|
One of these codes is very critical, which is also the code to ensure that each composite number is filtered only once:
| if i % prime == 0: break |
|---|
When i% prime == 0, prime is the prime factor of i, so i = x (a certain number) * prime. When one of the following prime numbers prime2 goes to sieve i * prime2, i * prime2 == x * prime * prime2, so prime and prime2 are both prime factors of i * prime2. But because prime< prime2, the smallest prime factor of i * prime2 is prime instead of prime2. So in order to avoid repeated screening of composite numbers, when i% prime == 0, break directly.
For example: i=2 filters 4, i=3 filters 6 and 9, but when i=4, prime is 2 first, and 8 is filtered out, but it breaks directly when it runs to I% prime == 0 , It avoids sifting out 12 when traversing prime = 3, and 12 is sifted out when i = 6 and prime = 2.
**The stronger the ability, the greater the responsibility. **
**Seek truth from facts, rigorous and meticulous. **
[Produced by the where2go team]
END
Intern Editor | Wang Wenxing
Responsible Editor | Joy
Recommended Posts