Want to quickly screen out primes within a certain upper limit ？
The following method can ensure that every composite number in the range is deleted （ stay bool The array is marked as a non prime number ）, And any composite number is only ：
“ Minimum prime factor × Maximum factor （ Not yourself ） = This composite number ”
The way to delete . Because each number is screened only once , The time complexity is O(n).
First browse how to realize it, and then talk about the principle .
#include <cstdio>
#include <cstring>
bool isPrime[100000010];
//isPrime[i] == 1 Express ：i Prime number
int Prime[6000010], cnt = 0;
//Prime Prime number
void GetPrime(int n)// Sieve to n
{
memset(isPrime, 1, sizeof(isPrime));
// With “ Every number is prime ” Is the initial state , Delete... One by one
isPrime[1] = 0;//1 Not primes
for(int i = 2; i <= n; i++)
{
if(isPrime[i])// Didn't sift out
Prime[++cnt] = i; //i Become the next prime
for(int j = 1; j <= cnt && i*Prime[j] <= n/* Don't exceed the upper limit */; j++)
{
// from Prime[1], That is, the minimum prime number 2 Start , Enumerate known prime numbers one by one , And expect Prime[j] yes (i*Prime[j]) The minimum prime factor of
// Of course ,i It's definitely better than Prime[j] Big , because Prime[j] Is in i What we got before
isPrime[i*Prime[j]] = 0;
if(i % Prime[j] == 0)//i Also contains Prime[j] This factor
break; // major measure . See principle
}
}
}
int main()
{
int n, q;
scanf("%d %d", &n, &q);
GetPrime(n);
while (q--)
{
int k;
scanf("%d", &k);
printf("%d\n", Prime[k]);
}
return 0;
}
import time
def get_prime(x):
for i in range(2,x+1):
if st[i]:
primes.append(i)
for j in range(len(primes)):
if primes[j]*i>x:
break
st[primes[j]*i]=False
if i%primes[j]==0:
break
start=time.time()
n=10000
N=n+5
st=[True]*N
primes=[]
get_prime(n)
print(len(primes))
end=time.time()
print(' Program running time ',end-start)
with open('./primes.txt','w') as f:
f.write('\n'.join(map(str,primes)))
In the code , Outer enumeration i=1→n. For one ii, After the bloody rain in front , If it hasn't been sifted out , Just add it to the prime array Prime[] in . next step , Yes, it is i To sift out a wave number .
The inner layer enumerates from small to large Prime[j].i×Prime[j] It's a composite number that you try to sift out , among , We expect Prime[j] Is the smallest prime factor of this composite number ( This is the condition of linear complexity , It's called “ Sieve condition ”). How is it guaranteed ？
j In the cycle of , One sentence has achieved this ：
if(i % Prime[j] == 0)
break;
j Loop to i \mod Prime[j] == 0imodPrime[j]==0 The reason why it just needs to stop is ：
The following is used s(smaller) Say less than j Number of numbers ,L(larger) Greater than j Number of numbers .
① i The minimum prime factor of must be Prime[j].
（ If i The minimum prime factor of is Prime[s] , that Prime[s] Enumerated earlier to （ Because we enumerate prime numbers from small to large ）, At that time break）
since ii The minimum prime factor of is Prime[j], that i×Prime[j] The minimum prime factor of is also Prime[j]. therefore ,j Itself is consistent with “ Sieve condition ” Of .
②i×Prime[s] The minimum prime factor of is indeed Prime[s].
（ If its minimum prime factor is a smaller prime number Prime[t], Well, of course. Prime[t] Enumerated earlier to , At that time break）
This explanation j Before （ use i×Prime[s] The way to sift numbers , The minimum prime factor is used ） All conform to “ Sieve condition ”.
③ i × Prime[L] The minimum prime factor of must be Prime[j].
（ because i The minimum prime factor of is Prime[j], therefore i×Prime[L] It also contains Prime[j] This factor （ This is a i Credit ）, So the minimum prime factor is also Prime[j]（ The new prime factor Prime[L] It's too big ））
This explanation , If j Keep increasing （ Will be with i×Prime[L] The way to sift numbers , The minimum prime factor is not used ）, Is not in line with “ Sieve condition ” Of .
tip ：
When ii When I was young , A large number of composite numbers may be screened out in one layer , It seems to take a lot of time , However, due to the guarantee that the sieved aggregate will not be sieved in the future （ Only screen once in total ）, Complexity is linear . To ii near nn when , There is almost nothing to do on each floor .
