nefu109 云之遥--素数 埃拉托斯尼斯筛法的应用
转载一个例子：
例子：
MAXN = 30:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
----------------------------------
从第一个素数2开始：
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
删除2的倍数（除本身外）后：
*2 3 5 7 9
11 13 15 17 19
21 23 25 27 29
下一个素数为3，删除3的倍数（同上）后。
*2 *3 5 7
11 13 17 19
23 25 29
重复上述操作。
最终筛出来的素数表如下：
2 3 5 7 11 13 17 19 23 29
这道题目刚开始给出n的范围是 2 000 000 000，后来改成1000了，但是我们还是按照以前的来，n很大 所以用一般法 肯定超时的 这时候 就用到了 埃拉托斯尼斯筛法
#include<iostream>#include<cstdio>#include<list>#include<algorithm>#include<cstring>#include<string>#include<queue>#include<stack>#include<map>#include<vector>#include<cmath>#include<memory.h>#include<set>#define ll long long#define LL __int64#define eps 1e-8#define e 2.718281828////const ll INF=9999999999999;#define M 400000100#define inf 0xfffffffusing namespace std;//vector<pair<int,int> > G;//typedef pair<int,int> P;//vector<pair<int,int>> ::iterator iter;////map<ll,int>mp;//map<ll,int>::iterator p;////vector<int>G[30012];bool isprime[50012];ll prime[50012];void dopprime()//埃拉托斯尼斯筛法，这个完全可以作为一个模版{memset(isprime,true,sizeof(isprime));int cnt=0;isprime[1]=0;for(ll i=2;i<=50012;i++){if(isprime[i]){prime[++cnt]=i;for(ll j=i*i;j<50012;j+=i)isprime[j]=false;}}}bool ifprime(ll x)//一般判素数法{double k=sqrt(double(x));for(int i=1;prime[i]<=k;i++)if(x%prime[i]==0)return 0;return 1;}int main(void){dopprime();ll n;while(cin>>n){if(n==1){puts("NO");continue;}if(ifprime(n))puts("YES");elseputs("NO");}}