ACM算法模板 线性筛与欧拉函数（欧拉筛）

线性筛

我们可以用线性筛去求质数（素数）

首先来一个根据定义的笨方法，就是写循环一个一个去判断 $n$ 能不能被1~ n \sqrt{n} n ​ 中的数整除。时间复杂度为O（n n \sqrt{n} n ​）,代码如下：

#include 
#include 
#include  //限制非法的函数调用int isprime (int x)
{int i,m;assert(x>=0); //强制x符合要求才执行程序if (x==1||x==0)//0与1都不是质数return 0;m=floor((sqrt(x)+0.5)); //返回一个小于传入参数的最大整数，加0.5是模拟四舍五入的过程for (i=2; i<=m; i++){if (x%i==0) return 0;return 1;}
}int main ()
{int i,n;while (~scanf("%d",&n)){if (isprime(n))printf( "Yes\n");else printf("No\n");}return 0;
}

线性筛则避免了重复的判断，时间复杂度为O（n）。
下面为代码，
输入一个上限n
输出1 ~ n 之间质数的个数

#include 
#include 
using namespace std;
//筛选1~n中所有的素数,保存到prime数组中,cnt为素数的个数
//vis数组标记是否为素数,0表示是素数，1表示不是素数int Make_Prime(int n)  //时间复杂度O(n)
{int cnt = 0;int vis[10000];//根据情况自己开数组int prime[10000];memset(vis, 0, sizeof(vis));for (int i = 2; i <= n; i ++){if (!vis[i])prime[cnt++] = i;for (int j = 0; j < cnt && i * prime[j] <=n; j ++){vis[i * prime[j]] = 1;if (i % prime[j] == 0)     //关键break;}}return cnt;
}int main()
{int n;while(cin >> n){cout<<Make_Prime(n)<<endl;}return 0;
}

将上述模板稍加修改即可判断质数
输入：n 代表建立1 ~ n 的质数表，之后输入m表示要判断的数字个数。
输出：是质数则为Yes ，不是质数为No

#include
#include
#includeusing namespace std;const int N=10000050;int n,m;
int pri[N];
//0代表不是质数,1代表是质数 void prepare(int n)
{memset(pri,1,sizeof(pri));pri[1]=0;//1不是质数 for(int i=2;i<=n;i++) {if(pri[i])//如果i是质数 {for(int j=2;j<=n/i;j++)pri[i*j]=0;//用i取标记合数 }}
}int main()
{scanf("%d%d",&n,&m);prepare(n);for(int i=1;i<=m;i++){int x;scanf("%d",&x);if(pri[x]) puts("Yes");else puts("No");}return 0;
}

欧拉函数

欧拉函数是求小于n的数中与n互质数字的个数。公式如下：

φ （ n ） = n ∗ ( 1 − 1 p 1 ) ∗ ( 1 − 1 p 2 ) ∗ ( 1 − 1 p 3 ) ⋯ ∗ ( 1 − 1 p i ) \varphi （n） = n*(1- \frac{1}{p1} \quad)*(1- \frac{1}{p2} \quad)*(1- \frac{1}{p3} \quad)\cdots *(1- \frac{1}{pi}) φ（n）=n∗(1−p11​)∗(1−p21​)∗(1−p31​)⋯∗(1−pi1​)

其中$pi$为n的质因数，对于n的一个质因数pi，因为n以内pi的倍数是均匀分布的，所以x以内有1/pi的数是pi的倍数，有 ( 1 − 1 p i ) (1- \frac{1}{pi} \quad) (1−pi1​)的数不是pi的倍数。对于pj，有1-1/pj的数不是pj的倍数，所以有 ( 1 − 1 p i ) (1- \frac{1}{pi} \quad) (1−pi1​)* ( 1 − 1 p j ) (1- \frac{1}{pj} \quad) (1−pj1​)的数既不是pi的倍数，也不是pj的倍数

eg: 求单个欧拉函数
输入：一个数，若输入为0则结束
输出：输出其欧拉函数的值

#include 
int Eular(int n)  //求单个数的欧拉函数
{int ans = n;for (int i = 2 ; i * i <= n ; i++){if (n % i == 0){ans =ans - ans / i;while (n % i == 0)n =n/i;  //消除i因子}}if (n > 1)		//n本身也是个质因子ans =ans -ans / n;return ans;
}
int main()
{int n;while (~scanf ("%d",&n) && n){if (n == 1)printf ("0\n");elseprintf ("%d\n",Eular(n));}return 0;
}

欧拉筛：

#include 
#include 
#include 
#define ll long long
using namespace std;
const int MAXN=100001;
int prime[MAXN+1];
int phi[MAXN+1];
void phi_prime()
{memset(prime,0,sizeof(prime));phi[1] = 1;for(int i=2; i<=MAXN; i++){if(!prime[i]){prime[++prime[0]] = i;phi[i] = i-1;//i为素数，小于i与i互质的数有i-1个}for(int j=1; j<=prime[0]&&i*prime[j]<=MAXN; j++){prime[prime[j]*i] = 1;if(i%prime[j]==0){phi[i*prime[j]] = phi[i]*prime[j];
//若prime[j]是i的质因子，则根据计算公式，i已经包括i*prime[j]的所有质因子
//prime数组 中的素数是递增的,当 i 能整除 prime[j]，那么 i*prime[j+1] 这个合数肯定被 prime[j] //乘以某个数筛掉,设这个数为m 证明如下
// i = k*prime[j] i*prime[j+1] = k*prime[j]*prime[j+1] = m*prime[j]
//因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。break;}else{phi[i*prime[j]] = phi[i]*(prime[j]-1);
//实际上就是 phi[i * prime[j]] = phi[i] * phi[prime[j]];
//性质 若m,n互质，则 φ(m?n)=φ(m)?φ(n)。特殊的，当m=2，n为奇数时，φ(2*n)=φ(n)。}}}}int main()
{phi_prime();int n;while(1){scanf("%d",&n);if (n==0) break;printf("%d\n",phi[n]);}return 0;
}

欧拉筛运用了3个欧拉函数的性质，大家如果对欧拉函数有兴趣的话，请移步至欧拉函数性质证明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！