线性筛素数欧拉函数

线性筛素数：

(关键代码为当i%prime[j]==0的时候跳出。)

#include <iostream> //线性筛素数。 #include <cstring> using namespace std; const int inf=1e6+7; int flag[inf]; //表示的是inf是不是质数，0表示不是，1表示是。 int prime[inf]; int k=0; void findprime(int n) {for(int i=2;i<=n;i++){if(!flag[i]) //说明i是素数。看来还是要使用素数的，因为欧拉筛是依照素数来进行筛后边的数据的。 {prime[k++]=i; //添加上素数.} for(int j=0;j<k&&prime[j]*i<=n;j++){flag[ prime[j]*i ]=1; //标记和数。 if(i%prime[j]==0)break; } } } int main() {int n;scanf("%d",&n);memset(flag,0,sizeof(flag));findprime(n);for(int i=0;i<k;i++)printf("%d\n",prime[i]);return 0; }

欧拉函数：

#include <iostream> //欧拉函数。 #include <cstring> using namespace std; const int inf=1e6+7; int phi[inf]; //phi[i]的含义是i 的欧拉函数值是多少？也就是说有几个数字和i是互质的。 int flag[inf]; int prime[inf]; //记录素数，标记素数。 int k=0; void euler(int n) {phi[1]=1; //特例。 for(int i=2;i<=n;i++){ if(!flag[i]) //说明i是质数。 {phi[i]=i-1; prime[k++]=i;} for(int j=0;j<k&&prime[j]*i<=n;j++){if(prime[j]*i>n)break;flag[prime[j]*i]=1; //标记和数。 if(i%prime[j]==0) //求质因数。 { phi[i*prime[j]]=phi[i]*prime[j];break; } elsephi[i*prime[j]]=phi[i]*phi[prime[j]]; }} }int main() {int n;scanf("%d",&n);memset(flag,0,sizeof(flag));euler(n); for(int i=1;i<=n;i++)printf("%d %d\n",i,phi[i]); return 0; }

 

总结

以上是生活随笔为你收集整理的线性筛素数欧拉函数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。