筛选素数

 1 #include <cstdio>
 2 #include <iostream>
 3 
 4 using namespace std;
 5 const int maxn 10000000  
 6 bool visit[maxn+3];  
 7 int prime[maxn], n; ///prime存1～n的所有素数、大概有(x / lnx)个  
 8 
 9 void getprime() {  
10     memset(visit, false, sizeof(visit));  
11     int num = 0;  
12     for (int i = 2; i <= n; i++) {  
13         if ( !visit[i] )  prime[++num] = i;  
14         for (int j = 1; j <= num && i * prime[j] <= n ;  j++) {  
15             visit[ i  *  prime[j] ]  =  true;  
16             if (i % prime[j] == 0) break; //点睛之笔
17         }  
18     }  
19 }