写在前面：
记录了个人的学习过程，同时方便复习
目录 |
有时候需要筛出来一张素数表，即1~n范围内的所有素数
一个个枚举判断是否为素数显然太慢
根据[◹]算术基本定理，如果存在正整数k(k>2)不是素数，那么它的因子里面一定包含之前的素数
这样的话，开一个boolean数组标记一下不是素数的数，筛到它们的时候跳过就好
详见埃拉托斯特尼筛法
但是如果这样筛，显然会有重复的筛除啊
比如6筛去了42，7也筛去了42
这样的情况还有很多很多，十分影响效率，时间上并不是线性的
但如果按照一个数的最小素因子把这个数排除掉，就没问题了！
代码如下：
C++：
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 int const MAXN=100010; 6 7 int prime[MAXN],tot; 8 bool notprime[MAXN]; 9 10 void pony_prime(int n){ 11 notprime[0]=1; 12 notprime[1]=1; 13 for(int i=2;i<=n;++i){ 14 if(!notprime[i]) 15 prime[tot++]=i; 16 for(int j=0; j<tot && i*prime[j]<=n;++j){ 17 notprime[i*prime[j]]=1; 18 if(i%prime[j]==0) break; 19 } 20 } 21 } 22 23 int main(int argc,char *argv[],char *enc[]){ 24 int m=100; 25 pony_prime(m); 26 for(int i=1;i<=m;++i){ 27 if(notprime[i]) printf("%d ",i); 28 else printf("%d Prime ",i); 29 } 30 return 0; 31 }
Java：
1 class pony{ 2 3 static int MAXN=100010; 4 5 static int[] prime=new int[MAXN]; 6 static int tot=0; 7 static boolean[] notprime=new boolean[MAXN]; 8 9 static void pony_prime(int n){ 10 notprime[0]=true; 11 notprime[1]=true; 12 for(int i=2;i<=n;++i){ 13 if(!notprime[i]) 14 prime[tot++]=i; 15 for(int j=0; j<tot && i*prime[j]<=n;++j){ 16 notprime[i*prime[j]]=true; 17 if(i%prime[j]==0) break; 18 } 19 } 20 } 21 22 public static void main(String[] args) throws Exception { 23 int m=100; 24 pony_prime(m); 25 for(int i=1;i<=m;++i){ 26 if(notprime[i]) System.out.println(i); 27 else System.out.println(i+" Prime"); 28 } 29 } 30 31 }
欧拉函数有以下五条性质：
由此，我们可以在素数线性筛的基础上筛出欧拉函数！
每次想要得到phi[n]，详细过程如下：
若n为素数，根据①，有phi[n]==n-1
若a*b==n(a，b为任意互质数)，根据②，有phi[n]==phi[a]*phi[b]，这里的phi[a]和phi[b]都是已经得到的
若a*p==n(p为质数，且p是a的因数)，根据⑤得phi[n]==phi[a]*p
代码如下：
C++：
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 int const MAXN=100010; 6 7 int prime[MAXN],tot; 8 bool notprime[MAXN]; 9 int euler[MAXN]; 10 11 void pony_getPhi(int n){ 12 notprime[0]=1; 13 notprime[1]=1; 14 euler[1]=1; 15 for(int i=2;i<=n;++i){ 16 if(!notprime[i]) 17 { 18 prime[tot++]=i; 19 euler[i]=i-1;//HERE 1 20 } 21 for(int j=0; j<tot && i*prime[j]<=n;++j){ 22 notprime[i*prime[j]]=1; 23 if(i%prime[j]==0){euler[i*prime[j]]=euler[i]*prime[j];break;}//HERE 5 24 else euler[i*prime[j]]=euler[i]*euler[prime[j]];//HERE 2 25 } 26 } 27 } 28 29 int main(int argc,char *argv[],char *enc[]){ 30 int m=100; 31 pony_getPhi(m); 32 for(int i=1;i<=m;++i){ 33 printf("phi(%d):%d",i,euler[i]); 34 if(notprime[i]) printf(" "); 35 else printf(" [%d]Prime ",i); 36 } 37 return 0; 38 }
Java：
1 class Pony{ 2 3 static int MAXN=100010; 4 5 static int[] prime=new int[MAXN]; 6 static int tot=0; 7 static boolean[] notprime=new boolean[MAXN]; 8 static int[] euler=new int[MAXN]; 9 10 static void pony_getPhi(int n){ 11 notprime[0]=true; 12 notprime[1]=true; 13 euler[1]=1; 14 for(int i=2;i<=n;++i){ 15 if(!notprime[i]) 16 { 17 prime[tot++]=i; 18 euler[i]=i-1;//HERE 1 19 } 20 for(int j=0; j<tot && i*prime[j]<=n;++j){ 21 notprime[i*prime[j]]=true; 22 if(i%prime[j]==0){euler[i*prime[j]]=euler[i]*prime[j];break;}//HERE 5 23 else euler[i*prime[j]]=euler[i]*euler[prime[j]];//HERE 2 24 } 25 } 26 } 27 28 public static void main(String[] args) throws Exception { 29 int m=100; 30 pony_getPhi(m); 31 for(int i=1;i<=m;++i){ 32 System.out.printf("phi(%d):%d",i,euler[i]); 33 if(notprime[i]) System.out.println(""); 34 else System.out.println(" ["+i+"]Prime"); 35 } 36 } 37 38 }
莫比乌斯函数μ(d)的定义如下：
(1)若d=1，那么μ(d)=1
(2)若d=p1p2…pk(p1…pk均为互异质数)，那么μ(d)=(−1)^k
(3)其他情况下，μ(d)=0
只要抓住定义就能轻松筛出莫比乌斯函数啦
代码如下：
C++：
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 int const MAXN=100010; 6 7 int prime[MAXN],tot; 8 bool notprime[MAXN]; 9 int miu[MAXN]; 10 11 void pony_getMiu(int n){ 12 notprime[0]=1; 13 notprime[1]=1; 14 miu[1]=1;//HERE 1 15 for(int i=2;i<=n;++i){ 16 if(!notprime[i]) 17 { 18 prime[tot++]=i; 19 miu[i]=-1;//HERE 2 20 } 21 for(int j=0; j<tot && i*prime[j]<=n;++j){ 22 notprime[i*prime[j]]=1; 23 if(i%prime[j]==0){miu[i*prime[j]]=0;break;}//HERE 3 24 else miu[i*prime[j]]=-1*miu[i];//HERE 2 25 } 26 } 27 } 28 29 int main(int argc,char *argv[],char *enc[]){ 30 int m=100; 31 pony_getMiu(m); 32 for(int i=1;i<=m;++i){ 33 printf("miu(%d):%d",i,miu[i]); 34 if(notprime[i]) printf(" "); 35 else printf(" [%d]Prime ",i); 36 } 37 return 0; 38 }
Java：
1 class Pony{ 2 3 static int MAXN=100010; 4 5 static int[] prime=new int[MAXN]; 6 static int tot=0; 7 static boolean[] notprime=new boolean[MAXN]; 8 static int[] miu=new int[MAXN]; 9 10 static void pony_getMiu(int n){ 11 notprime[0]=true; 12 notprime[1]=true; 13 miu[1]=1;//HERE 1 14 for(int i=2;i<=n;++i){ 15 if(!notprime[i]) 16 { 17 prime[tot++]=i; 18 miu[i]=-1;//HERE 2 19 } 20 for(int j=0; j<tot && i*prime[j]<=n;++j){ 21 notprime[i*prime[j]]=true; 22 if(i%prime[j]==0){miu[i*prime[j]]=0;break;}//HERE 3 23 else miu[i*prime[j]]=-1*miu[i];//HERE 2 24 } 25 } 26 } 27 28 public static void main(String[] args) throws Exception { 29 int m=100; 30 pony_getMiu(m); 31 for(int i=1;i<=m;++i){ 32 System.out.printf("miu(%d):%d",i,miu[i]); 33 if(notprime[i]) System.out.println(""); 34 else System.out.println(" ["+i+"]Prime"); 35 } 36 } 37 38 }
有木有觉得莫比乌斯函数超级好筛？
