功能:高效率得到1～n范围内的所有素数.
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 }