歐拉發現求小於等於n的正整數中有多少個數與n互質可以用這個公式:
euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中p1,p2……pn為x的所有素因數,x是不為0的整數。euler(1)=1(唯一和1互質的數就是1本身)。
歐拉公式的延伸:一個數的所有質因子之和是euler(n)*n/2。
其實直接看模板加注解想想就能看懂
篩選的原理就是找出n的因子,剔除含有n的因子的數,即剔除與n不互質的數
既然是求與n互質的個數,那我們可以直接篩選,看模板:
int phi(int n)
{ int res=n; /假設現有n個數與n互質,開始篩選剔除
for(i=2;i*i<=n;i++)
{ if(n%i==0) /若這個數是n的因子,減去n以下含有這個因子的數個數,假設n=8,小於等於8,2為公因子的有8/2=4個
{ res-=res/i;
while(n%i==0) /將n不斷整除這個因子
n=n/i;
}
}
if(n>1) /若n大於1,則此時的n也是一個除1以外的因子
res-=res/n;
return res;
}
有時候還用到多個數的歐拉值,因此需要對1到n的數都求出歐拉值,就是打表。
將1到n的歐拉值求出並存儲到數組,篩選法,代碼:
void phi(int n) 上邊的看懂了,下邊這個求多個數的也類似
{ for(int i=1;i<=n;i++)
p[i]=i; 賦原值
for(int i=2;i<=n;i++)
if(p[i]==i)
{ for(int j=i;j<=n;j+=i) 篩選
p[j]=p[j]-p[j]/i;
}
}
原理就是若一個數有除1和它本身以外的因子就將它標記不是素數,最後無標記的就是素數。
直接看代碼加注解:
#include <iostream>
#include <cstring>
#define MAX 1000001
int flag[MAX];
int main()
{ memset(flag,0,sizeof(flag));
flag[1]=1; /1代表不是素數,0代表是素數
for(int i=4;i<MAX;i+=2)
flag[i]=1; /先將偶數先標記不是
for(int i=3;i*i<MAX;i+=2)
for(int j=i*i;j<MAX;j+=i) /奇數的倍數標記不是
flag[j]=1;
int n;
while(cin>>n)
{ if(flag[n]==0)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
素數篩常用於讓你判斷大量素數,或求大量素數,當然如果數目很少,就按常規判斷就好了
待續……