先來最基本的線性篩素數(shù)，以后的算法其實都是基于這個最基本的算法：
1 #include<stdio.h>
2 #include<string.h>
3 #define M 10000000
4 int prime[M/3];
5 bool flag[M];
6 void get_prime()
7 {
8 int i,j,k;
9 memset(flag,false,sizeof(flag));
10 k=0;
11 for(i=2;i<M;i++){
12 if(!flag[i])
13 prime[k++]=i;
14 for(j=0;j<k&&i*prime[j]<M;j++){
15 flag[i*prime[j]]=true;
16 if(i%prime[j]==0)
17 break;
18 }
19 }
20 }
21 int main()
22 {}
利用了每個合數(shù)必有一個最小素因子，每個合數(shù)僅被它的最小素因子篩去正好一次，所以是線性時間。
代碼中體現(xiàn)在： if(i%prime[j]==0) break;
-----------------------------------------------------------------------我是低調(diào)的分割線------------------------------------------------------------------------------------------
然后可以利用這種線性篩法求歐拉函數(shù)，需要用到以下幾個性質(zhì)：
//(1) 若(N%a==0 && (N/a)%a==0) 則有:E(N)=E(N/a)*a;
//(2) 若(N%a==0 && (N/a)%a!=0) 則有:E(N)=E(N/a)*(a-1);
其中a是N的質(zhì)因數(shù)。
關(guān)于歐拉函數(shù)還有以下性質(zhì)：
(1) phi[p]=p-1; (p為素數(shù));
(2)若N=p^n(p為素數(shù))，則 phi[N]=(p-1)*p^(n-1);
關(guān)于歐拉函數(shù)，Wiki有很詳細的介紹。
1 #include<stdio.h>
2 #include<string.h>
3 #define M 10000000
4 int prime[M/3],phi[M];
5 bool flag[M];
6 void get_prime()
7 {
8 int i,j,k;
9 memset(flag,false,sizeof(flag));
10 k=0;
11 for(i=2;i<M;i++){
12 if(!flag[i]){
13 prime[k++]=i;
14 phi[i]=i-1;
15 }
16 for(j=0;j<k&&i*prime[j]<M;j++){
17 flag[i*prime[j]]=true;
18 if(i%prime[j]==0){
19 phi[i*prime[j]]=phi[i]*prime[j];
20 break;
21 }
22 else
23 phi[i*prime[j]]=phi[i]*(prime[j]-1);
24 }
25 }
26 }
27 int main()
28 {}
-----------------------------------------------------------------------我是低調(diào)的分割線-----------------------------------------------------------------------------------------
求約數(shù)個數(shù)略微復雜一點，但大體還是那個意思。
約數(shù)個數(shù)的性質(zhì)，對于一個數(shù)N，N=p1^a1 + p2^a2 + ... + pn^an。其中p1 ,p2, p3... pn是N的質(zhì)因數(shù)，a1 ,a2, a2,...an為相應的指數(shù)，則
div_num[N]=(p1+1)*(p2+1)*(p3+1)* ... *(pn+1);
結(jié)合這個算法的特點，在程序中如下運用：
對于div_num：
(1)如果i|prime[j] 那么 div_num[i*prime[j]]=div_sum[i]/(e[i]+1)*(e[i]+2) //最小素因子次數(shù)加1
(2)否則 div_num[i*prime[j]]=div_num[i]*div_num[prime[j]] //滿足積性函數(shù)條件
對于e：
(1)如果i|pr[j] e[i*pr[j]]=e[i]+1; //最小素因子次數(shù)加1
(2)否則 e[i*pr[j]]=1; //pr[j]為1次
1 #include<stdio.h>
2 #include<string.h>
3 #define M 10000000
4 int prime[M/3],e[M/3],div_num[M]; // e[i]表示第i個素數(shù)因子的個數(shù)
5 bool flag[M];
6 void get_prime()
7 {
8 int i,j,k;
9 memset(flag,false,sizeof(flag));
10 k=0;
11 for(i=2;i<M;i++){
12 if(!flag[i]){
13 prime[k++]=i;
14 e[i]=1;
15 div_num[i]=2; //素數(shù)的約數(shù)個數(shù)為2
16 }
17 for(j=0;j<k&&i*prime[j]<M;j++){
18 flag[i*prime[j]]=true;
19 if(i%prime[j]==0){
20 div_num[i*prime[j]]=div_num[i]/(e[i]+1)*(e[i]+2);
21 e[i*prime[j]]=e[i]+1;
22 break;
23 }
24 else{
25 div_num[i*prime[j]]=div_num[i]*div_num[prime[j]];
26 e[i]=1;
27 }
28 }
29 }
30 }
31 int main()
32 {}
33
34
35
希望大家有所收獲~~
Made by M.J