Problem: Find all prime numbers within a given range n
A prime number is a positive integer that has no positive integer divisors other than 1 and itself.
There are a lot of ways to print all the prime number within range n.
Method 1: The most direct method is to start from the definition. For any integer p, use p to divide all the number between 2 and p-1. If p is found to be divisible, p is not prime. Obviously, the efficiency of this method is simply unacceptable, and the optimization space is very large.
Method Two: Obviously, even numbers are not prime numbers. For any odd number p, use p to divide all the numbers between 3 and p-2 with the gap 2. If p is found to be divisible, then p is not prime. The efficiency of this method is slightly higher, but its essence is no different from method 1, except that the range of divisible coefficients is reduced to odd numbers
Method three: Using the idea of prime factorization, for any odd p, use a prime number less than p to divide p. If p is found to be divisible, p is not a prime number. The computational efficiency of this method is improved again.
Method four: Using the square root condition, for any odd p, divide p with a prime number less than the square root of p. If p is found to be divisible, p is not prime
However, all the four methods above is not fast enough, for example it took me 13.54 second to print all the prime numbers under 2 to the power of 22.
The method below is called the screening method:
(1) Put all n numbers into the array and set them to a positive state
(2) Set all numbers whose subscripts of the array are even numbers to the negative state
(3) Traverse the square root numbers of the length of the array in turn
(4) If the current number is in a positive state, set the digital state of its multiple to negative
If we use the second method, we only use 1.16 second to find all the prime number under 2 to the power of 22. It makes the speed go 10 times faster.
Below is my code using the screening method:
max_num = int(input("Input a maximum number.\n"))
prime_flag = list();
for i in range(0, max_num):
prime_flag.append(1)
prime_flag[0] = 0
prime_flag[1] = 0
count = 0
for i in range(1, max_num):
if i * i > max_num:
break
if prime_flag[i] == 0:
continue
for j in range(i + i, max_num, i):
prime_flag[j] = 0
for i in range(1, max_num):
if prime_flag[i] == 1:
print(i)
count += 1
print(f"The number of prime number under {max_num} is {count}")