BDFZOI 数论小结1（筛法、欧拉phi函数）

Eratothenes筛法

描述

找出N以内的素数，并求和。

输入一个正整数N，N<=10^7输出一个整数，表示N以内素数之和。

样例输入

样例输出

提示

1.结果可能很大
2.Eratosthenes筛法的复杂度为O(NlglgN)，能在1s内找出10^7以内的素数

代码：

 1 #include<iostream>
 2 using namespace std;
 3 int a[10000005];
 4 int n;
 5 int main(){
 6     cin>>n;
 7     int i, j;
 8     for(i = 2; i <= n/2; i++){
 9         if(a[i]==0)
10         for(j = i; j <= n/i; j++){
11             a[i*j] = -1;
12         }
13     }
14     long long ans = 0;
15     for(i = 2; i <= n; i++){
16         if(a[i]!=-1) 
17             ans+=i;
18     }
19     cout<<ans<<endl;
20     return 0;
21 }

备注：

筛法的思想很简单。从2开始，把2的所有倍数标记为-1，再找到下一个未被标记的数（质数），继续划掉它的倍数。注意j从i开始循环就好了，因为更小的倍数已经在之前删更小的质数倍数的时候删过了。

答案用long long存。。

欧拉Phi函数

描述

在数论中，对于正整数n，函数phi(n)的值是"小于等于n的数中，与n互质的数的个数”。

也可以用下面公式计算：phi(n)=n×(1-1/p1)×(1-1/p2)...×(1-1/pm)，其中p1,p2...pm为n的所有质因数（即又是质数又是n的因数）。

输入一个正整数n，n<=10^7输出一个整数，既phi(n)的值

样例输入

样例输出

提示

45有质因数3和5，那么phi(45)=45(1-1/3)(1-1/5)=24
n本身也是自己的因数，但不一定是质数

代码：

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdlib>
 4 using namespace std;
 5 int num;
 6 int a[10000005];
 7 int phi(int n){
 8     int ans = n;
 9     int m = (int)sqrt(n+0.5);
10     int i;
11     for(i = 2; i <= m; i++){
12         if(n%i == 0){
13             ans = ans/i*(i-1);
14             while(n%i == 0) n/=i;
15         }
16     }
17     if(n > 1)ans = ans/n*(n-1);
18     return ans;
19 }
20 int main(){
21     cin>>num;
22     int ans = phi(num);
23     cout<<ans<<endl;
24     return 0;
25 }

备注：

参考《入门经典》。其实也是运用了筛法的思想。最开始我用先生成素数表再逐个判断虽然慢点也AC了。实际上，从2开始，每找到一个素因子就把它除干净，这样保证找到的每一个因子都是素数。注意：i循环到√n就可以了，因为最多只会有一个大于√n的素因子（两个的话乘起来不就超了么），最后加一个if（n>1）把最后那个最大的素因子算上就好了。

欧拉Phi函数升级版

描述

在数论中，对正整数n，phi(n)的值是"小于等于n的数中，与n互质的数的个数”，并且也是模n乘法群Z_n^*的规模。

可以用下面公式计算：phi(n)=n(1-1/p1)(1-1/p2)...(1-1/pm)，其中p1,p2...pm为n的所有质因数。

输入一个正整数n，n<=10^5输出一个整数，phi(1)+phi(2)+...+phi(n)的值

样例输入

样例输出

提示

1.结果可能很大
2.O(NlogN)才能过，借鉴Eratosthenes筛法

代码：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int phi[100005];
 5 void phi_table(int n){
 6     memset(phi, 0, sizeof(phi));
 7     phi[1] = 1;
 8     for(int i = 2; i <= n; i++)
 9         if(!phi[i])
10             for(int j = i; j <= n; j+=i){
11                 if(!phi[j]) phi[j]=j;
12                 phi[j] = phi[j]/i*(i-1);
13             }
14 }
15 int main(){
16     int num;
17     cin>>num;
18     phi_table(num);
19     long long ans = 0;
20     int i;
21     for(i = 1; i <= num; i++)
22         ans+=phi[i];
23     cout<<ans;
24     return 0;
25 }

备注：

参考《入门经典》。

升级版就是求1~n所有phi（x）之和。phi(1)=1..

从2开始循环，如果phi[i]==0的话说明这个数是质数。然后开始筛，对于所有i的倍数，如果还为0，就让它等于本身。然后把phi[j]乘上这个1-1/该素因子。相当于每处理一个数就把1~n内所有以它为素因子的数都处理了。

这样就实现了NlogN的复杂度？？