。。 就是先暴力算出2*10^8次方内素数的个数 大概有10^7个 因为范围是2*10^8 如果普通打表就要开这么大的数组,开不下 于是把2*10^8分成了100个区间 每个区间长度是2*10^6 然后分开用筛法计算 相当于计算100个区间素数个数 这样的话就只需要开10^7+2*10^6这么大的数组
#include#include #include #include using namespace std;#define ll long long#define LIM (int)2e8#define K 1bool Make_prime_Vis[2000009];void Make_prime_1(int a[],int &len,const int N){memset(Make_prime_Vis,0,sizeof(Make_prime_Vis));for(int i=2;i*i<=N;i++){if(Make_prime_Vis[i]) continue;for(int j=i+i;j<=N;j+=i) Make_prime_Vis[j] = 1;}len = 0;for(int i=2;i<=N;i++) if(!Make_prime_Vis[i]){a[len++] = i;}}void Make_prime_2(int prime[],int &len,int l,int r){memset(Make_prime_Vis,0,sizeof(Make_prime_Vis));for(int i=0;prime[i]*prime[i]<=r;i++){int s = l/prime[i]*prime[i];if(s < l) s += prime[i];for(int j=s;j<=r;j+=prime[i]){ Make_prime_Vis[j-l] = 1;}}for(int i=0;i<=r-l;i++) if(!Make_prime_Vis[i])prime[len++] = i+l;}int prime[13000000],tot = 0;int main(){Make_prime_1(prime,tot,2000000);for(int i=2;i<=198;i+=2)Make_prime_2(prime,tot,i*(int)1e6+1,(i+2)*(int)1e6);int n;while(scanf("%d",&n) == 1){if(n == 1) {puts("0");continue;}int l = 0,r = tot,ans = -1;while(l < r){int mid = (l+r)/2;if(prime[mid] == n) {ans = mid+1;break;}else if(prime[mid] > n) r = mid;else l = mid+1;}if(ans != -1) printf("%d\n",ans);else printf("%d\n",l);}return 0;