Because to learn to write infiltration tools, these days are on python programming basics class, listening to me doze off, after all, I have learned it before. Finally sherry teacher left homework, one of the questions is this:
Topic: write python program to find prime numbers between 10-30.
It's so simple, I'll give a straight answer:
Prime = [11, 13, 17, 19, 23, 29] print(Prime)
Output results:
[11, 13, 17, 19, 23, 29]
Of course, this would certainly result in a public execution by Ms. Sherry in the next class, so it's better to write an algorithm based on what you learned in class.
1. Exhaustive method
Think back to the class learned variables, lists, loops and other things, sherry teacher also personally demonstrated multiple dead loop is how to get out of (the teacher is slippery hands or business is not skilled ah), so we still need to think carefully not to repeat the same mistakes.
Idea: First construct a loop that iterates over all eligible natural numbers, then one by one verify that they are prime, and finally list the eligible primes.
# The first exhaustive method that was coded was simple and brutal, just performance pulling across.
# P = factor, N = natural number
import time
t0 = () # Start time
Min = 10 # Range minimum
Max = 30 # Range maximum
Result = [] # Results
for N in range(Min, Max): # Give the natural numbers an iteration
for P in range(2, N):
if (N % P == 0): # Determine if there are factors
break # With a factor it's not prime, break out of the loop #
else:
(N)
print('Calculation', Min, 'to', Max, 'Between prime numbers')
print(Min, 'to', Max, Sequence of primes between ':', Result)
print(Min, 'to', Max, The number of primes between ':', len(Result))
print('Calculation time consumed:', () - t0, 'Seconds')Execution results (computation elapsed time is added at the end):
By this point the homework was done. I then finished a couple of other problems and realized I was bored, so I cut back to try and get something going. With this amount of computation, 0 seconds is really a bit low, so I might as well take this opportunity to bake the laptop's performance, so I'll just add a couple of zeros to the Min and Max values. try 100000-200000.
It's embarrassing, it's stuck straight away, the code is a bit of a pull across, not my style at all. Poured a cup of coffee and finally ran it.
This is too much, there must be something wrong, the code I wrote in C a long time ago wasn't that slow as I remember. Anyway, I've got the weekend free, so I might as well take a closer look at it.
2. Function (CV) method
To broaden my mind a bit, I decided to borrow some code from the big boys. I've heard that functions are a good thing, so I CV'd two of them.
One function determines primes, the other seeks all primes in the range, and putting them together, this is what it looks like:
# Learned it online, customized two functions, but it gets stuck with slightly larger values.
import time
t0 = ()
Min = 100000 # Range minimum
Max = 200000 # Range maximum
def is_prime(n): return 0 not in [n % i for i in range(2, n//2+1)] # Determine whether a number is prime or not
def gen_prime(a, b): return [n for n in range(
a, b+1) if 0 not in [n % i for i in range(2, n//2+1)]] # Prime numbers in the output range
print('Calculation', Min, 'to', Max, 'Between prime numbers')
print(Min, 'to', Max, Sequence of primes between ':', gen_prime(Min, Max))
print('Calculation time consumed:', () - t0, 'Seconds')Slightly altered, still 100,000-200,000, let's try it.
Well, as soon as it runs the fan starts whining and the CPU is baking. It seems the CV method doesn't work either. After a long bake, this time the result is even worse than the last time, more than 300 seconds, these two functions are still essentially an exhaustive method, it seems that this road is not going to work either.
3. Exhaustive reform
We can analyze the code of the exhaustive method to see if there is any improvement. First of all, through the nine years of compulsory education to master the knowledge of mathematics, we know that only 2 of the primes are even, so the calculation can be ignored the even numbers, only the odd numbers, the workload is immediately halved! Secondly, when determining whether N is prime by factoring P, if P is large enough, say when PxP>=N, then the loop that follows is actually repeated meaninglessly. Because assuming PxQ>=N, then one of P and Q must be less than sqrt(N), and it's just a matter of calculating the case where P<=sqrt(N).
Because 2 as the only even number, sandwiched inside the loop is troublesome to deal with, so put in the beginning to deal with away. The final code is as follows:
# Optimized code with fewer pointless loops is much faster than before.
import time
t0 = ()
Min = 100000 # Range minimum
Max = 200000 # Range maximum
Prime = [2, 3] # List of prime numbers
Result = [] # Results
Loop = 0 # Calculate the number of cycles
if Min <= 2:
(2)
if Min <= 3:
(3) # Get rid of the troublesome even number of two first #
for N in range(5, Max, 2):
for P in range(3, int(N**0.5)+2, 2): # Calculated only up to the root N
Loop += 1
if (N % P == 0):
break
else:
(N)
if N > Min:
(N)
print('Calculation', Min, 'to', Max, 'Between prime numbers')
print(Min, 'to', Max, Sequence of primes between ':', Result)
print(Min, 'to', Max, The number of primes between ':', len(Result))
print('Number of cycles:', Loop)
print('Calculation time consumed:', () - t0, 'Seconds')
The amount of code is more, but the effect is still obvious, 100000-200000 is only 0.4 seconds, I don't know how much faster, it seems like we are on the right track. I decided to add more to 1000000-500000000 to see if it would hold up. Because the output is too much the console will get stuck, so change it and only output the last prime number.
It took a total of 64 seconds, so it still seems like a bit of a chore.
4. Exhaustive magic
Let's analyze this a little more, what if the factors we use to determine, instead of using a list of odd numbers, we use the primes inside the generated Prime list, since there are far fewer primes than there are odd numbers, so the second loop would be less work? Could try it. But because of this change, you need to add some judgment statements into it, so the time saved is more limited.
# Don't look at this code as long, but it won't get stuck running up to 10 million, and it's fast.
import time
t0 = ()
Min = 1000000 # Range minimum
Max = 5000000 # Range maximum
Prime = [2, 3] # List of prime numbers
Result = [] # Results
Loop = 0 # Calculate the number of cycles
if Min <= 2:
(2)
if Min <= 3:
(3)
for N in range(5, Max, 2):
M = int(N**0.5) # The upper limit is the root sign N
for P in range(len(Prime)): # Iterate through Prime, the list of primes #
Loop += 1
L = Prime[P+1]
if (N % L == 0):
break
elif L >= M: # The upper limit is greater than the root N, determine the prime number and jump out of the loop
(N)
if N > Min:
(N)
break
print('Calculation', Min, 'to', Max, 'Between prime numbers')
print('The last prime number:', Result[-1])
print(Min, 'to', Max, The number of primes between ':', len(Result))
print('Number of cycles:', Loop)
print('Calculation time consumed:', () - t0, 'Seconds')Or 1,000,000-5,000,000 and try again.
This time it took 22 seconds, which is a big chunk of time again, but there doesn't seem to be much room for improvement anymore, and it feels like the exhaustive method has run its course and needs new ideas.
5. Echidna sieve method
In fact, in middle school math we learned the Echidna sieve method: if P is a prime number, then multiples of N greater than P must not be prime. If we eliminate all the combinations, then all the remaining numbers are prime. We can generate a list to store whether a number is prime or not, initially prime, and each time we come up with a prime number, we mark all its multiples as combinations.
# The speed has taken off.
import time
t0 = ()
Min = 1000000 # Range minimum
Max = 2000000 # Range maximum
Loop = 0 # Calculate the number of cycles
Result = [] # Results
Natural = [True for P in range(Max)] # The list of natural numbers is marked True
for P in range(2, Max):
if Natural[P]: # If the flag is True, it's prime.
if P >= Min:
(P) # Add primes within range
for N in range(P*2, Max, P): # Change the marking of multiples of prime numbers to False
Loop += 1
Natural[N] = False
print('Calculation', Min, 'to', Max, 'Between prime numbers')
print('The last prime number:', Result[-1])
print(Min, 'to', Max, The number of primes between ':', len(Result))
print('Number of cycles:', Loop)
print('Calculation time consumed:', () - t0, 'Seconds')
1.6 seconds, more than 10 times faster than the most advanced exhaustive method, is a triumph of math. Try 1-50,000,000 again.
It's great that it only takes 20 seconds. Because of the nature of the sieve method, ignoring the effect of memory, the higher the value, the faster the later instead.
6. Euler sieve method
We can carefully analyze, the above Echidna sieve method in the final mark, or overcounting something, N will repeat the mark False, such as 77, both a multiple of 7 and a multiple of 11, so it will be marked twice, followed by a large ensemble of numbers will repeat the mark many times, a waste of arithmetic, so the marking of the exclusion of ensembles. The other thing is that when P*N is greater than Max, the later calculations are no longer meaningful and should also be jumped out. Excluding these repetitive actions is the Euler sieve method, also called linear sieve.
# Final version, optimized for many details.
import time
t0 = ()
Min = 1 # Range minimum
Max = 50000000 # Range maximum
Loop = 0 # Calculate the number of cycles
Prime = [2]
Result = [] # Results
if Min <= 2:
(2)
Limit = int(Max/3)+1
Natural = [True for P in range(Max+1)] # The list of natural numbers is marked True
for P in range(3, Max+1, 2):
if Natural[P]: # If the flag is True, it's prime.
(P)
if P >= Min:
(P)
if P > Limit: # No need to sift beyond Limit, just continue #
continue
for N in Prime: # Change the marking of multiples of prime numbers to False
Loop += 1
if P*N > Max: # Over Max it's meaningless, just break.
break
Natural[P * N] = False
if P % N == 0: # Determine if a number is a combination
break
print('Calculation', Min, 'to', Max, 'Between prime numbers')
print('The last prime number:', Result[-1])
print(Min, 'to', Max, The number of primes between ':', len(Result))
print('Number of cycles:', Loop)
print('Calculation time consumed:', () - t0, 'Seconds')(Updated this code because the previous version was indented incorrectly)
The same conditions took 11.46 seconds. This is due to the extra list and a few lines of judgment statements, and the interpreted nature of python, so it's not actually several times faster, but it's still about a 50% improvement in overall efficiency.
To this point this article on python to calculate the prime number of 6 ways to introduce this article, more related python to calculate the prime number of content please search for my previous articles or continue to browse the following related articles I hope you will support me more in the future!