一、檢查n是否為素數
??
最簡單思路：所有可能的因數全部試一遍。
?
int gg(int n)
{for(int i=2;i<n;i++){if((n%i)==0)return 0;//有因數就不是素數咯}return 1;
}?
進一步思考：沒必要枚舉所有的數，每一個小于n^(1/2)的因數i，一定有一個大于n^(1/2)的因數j與之對應，也就是i*j=n，所以枚舉小于等于n^(1/2)的因數即可
?
int gg(int n)
{for(int i=2;i*i<=n;i++){if((n%i)==0)return 0;}return 1;
}?
二、約數枚舉
?上面已經說過，不需要枚舉所有因數，枚舉出某小因數以后算出對應的大因數即可。
vector<int> gg(int n)
{vector<int> a;for(int i=2;i*i<=n;i++){if((n%i)==0){a.push_back(i);if((n/i)!=i)a.push_back(n/i);//根號n的情況不要重復添加}}return a;
}?
三、埃氏篩法
?只對一個整數操作，O(N)，已經足夠了，如果對許多整數進行素性檢測，還有更高效的算法，比如埃氏篩法。
問題：枚舉n以內所有素數
操作：先把所有整數列出來，然后把2的倍數全部剔除，然后是三的，以此類推，遍歷所有素數，把倍數全部劃去。
對于每個數字i，如果沒被劃去，他一定是素數，因為他不是任何2到i-1數字的倍數。然后就開始劃它的倍數就好。
int a[maxx];
int b[maxx+1];
int gg(int n)
{int p=0;//記錄素數個數for(int i=0;i<n+1;i++)b[i]=1;b[0]=0;b[1]=0;//準備完畢for(int i=2;i<=n;i++){if(b[i]){a[p++]=i;//記錄素數和個數for(int j=2*i;j<=n;j+=i)b[j]=0;//剔除倍數}}return p;//返回素數個數
}四、區間篩法
?給定整數a和b，請問區間[a,b)內有多少個素數？?
思路：之前說過，因為b以內合數的最小質因數一定不超過sqrt(b),如果有sqrt(b)以內的素數表的話，就可以把篩選法用在[a,b)上了,先分別做好[2,sqrt(b))的表和[a,b)的表，然后從[2,sqrt(b))的表中篩得素數的同時，也將其倍數從[a,b)的表中劃去，最后剩下的就是區間[a,b)內的素數了。
//不gg了，這次就來個標準一點的吧
typedef long long ll;
bool is_prime[maxn];
bool is_prime_small[maxn];
void segment_sieve(ll a,ll b)
{for(ll i=0;i*i<b;++i) is_prime_small[i]=true; //初始化for(ll i=0;i<b-a;++i) is_prime[i]=true; //初始化，注意下標變化，為了省空間for(ll i=2;i*i<b;++i) {if(is_prime_small[i]) {for(ll j=2*i;j*j<b;j+=i) is_prime_small[j]=false; //篩選[2,sqrt(b));//(a+i-1)/i得到最接近a的i的倍數，最低是i的2倍，然后篩選for(ll j=max(2LL,(a+i-1)/i)*i;j<b;j+=i) is_prime[j-a]=false;}}
}五、線性實現
篩法很多數被處理了不止1遍，比如6，在素數為2的時候處理1次，為3時候又處理一次，因此又造成了不必要處理。O(nloglogn)已經基本可以滿足一般需要了。
本代碼保證每個合數只會被它的最小質因數篩去，因此每個數只會被標記一次，所以時間復雜度是O(n)
證明略
話不多說，上板子
#include<cstdio>
#include<cstring>
#define MAXN 100005
#define MAXL 1299710
int prime[MAXN];
int check[MAXL];
int tot = 0;
memset(check, 0, sizeof(check));
for (int i = 2; i < MAXL; ++i)
{if(!check[i])prime[tot++] = i;for (int j = 0; j < tot; ++j)//****************************************{if (i * prime[j] > MAXL)break;//*******************check[i*prime[j]] = 1;if (i % prime[j] == 0)break;//******}
}素數基本就這些內容咯。。。。
