1.质因数分解 2.素数测试 3.欧拉函数 4.大数分解与素数判定
素数又称质数，有无限个。除了1和它本身以外不再有其他的除数整除。
算术基本定理:每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。例如：6936=2^3*3*17^2，1200=2^4*3*5^2。
1.质因数分解 每个合数都可以写成几个素数相乘的形式，其中每个素数叫做这个合数的素因数。把一个合数用素因数相乘的形式表示出来，叫做质因数分解。 一般我们用短除法分解素因数，算法步骤如下： 1.先用一个能整除这个合数的素数（通常从最小的开始）去除。 2.得出的商如果是合数，再按照上面的方法继续除下去，直到得出的商是素数为止。 3.然后把各个除数和最后的商按从小到大的顺序写成连乘的形式。 注意：由于任何一个合数n至多会有一个大于根号n的因子。
int cut=0;//素因子个数 for(int=2;i*i<=n;i++) { if(n%i==0) { ++cut; p[cut]=i;//存素因子 num[cut]=0;//每个素因子的指数 while{n%i==0} { ++num[cut];//每个素因子的指数 n/=i; } } } if(n>1) { ++cut; p[cut]=n; num[cut]=1; }举例
#include<iostream> #include<cstring> using namespace std; int cnt,num[10010],p[10010]; void a(int n) { cnt=0; memset(num,0,sizeof(num)); memset(p,0,sizeof(p)); for(int i=2;i*i<=n;i++) { if(n%i==0) { ++cnt; p[cnt]=i; num[cnt]=0; while(n%i==0) { ++num[cnt]; n/=i; } } } if(n>1) { ++cnt; p[cnt]=n; num[cnt]=1; } } int main() { int n; while(cin>>n){ a(n); cout<<n<<"="<<p[1]<<"^"<<num[1]; for(int i=2;i<=cnt;i++) cout<<"*"<<p[i]<<"^"<<num[i]; cout<<endl; } return 0; }2.素数测试 判定一个数字p是不是质数：拿1 ~p 的所有数字来试除。
Eratosthenes筛法 算法描述： 1.列出所有正整数。 2.从2开始，删掉 2 的倍数。找下一个未被删掉的数字。 3.找到 3 ，删掉 3 的倍数。找下一个未被删掉的数字 4.找到 5 ，删掉 5 的倍数。 … 重复步骤，就能删掉所有合数，找到所有质数。
bool prime[20000000]; void eratosthenes() { memset(prime,1,sizeof(prime)); prime[0] = 0; prime[1] = 0; // 0 和 1 不是质数 for (int i=2; i<20000000; i++) if (prime[i]==1) // 删掉质数i的倍数 for (int j=i+i; j<20000000; j+=i) prime[j] = 0;注意：删掉质数 i 的倍数时，早已删掉1 倍~ i-1 倍之间的合数了，所以直接从i倍开始删除。
//代码可优化如下： void eratosthenes(){ memset(prime,1,sizeof(prime)); prime[0] = 0;prime[1] = 0; for (int i=2; i<20000000; i++) if (prime[i]==1) //删掉i的倍数从i倍开始。 for (int j=i*i; j<20000000; j+=i) prime[j] = 0;3.欧拉公式 （互质：公约数只有1的两个整数） 4.性质： a)当p为质数时, φ(p) = p – 1。 证明：因为小于本身的数都与该数互质，但是注意φ(1)=1.
b)对于互质的正整数a和n,有（a^φ(n)）(mod n) ≡ 1
c)费马小定理：若正整数a 与素数p 互质，则有（a^(p - 1)）mod p≡1 。 证明:由于性质a可知当p为质数，φ(p) = p -1，代入性质b即可证明。 d)当n为奇数时φ(2n)=φ(n). e)当n和m互质时,φ(n*m)=φ(n)*φ(m). f)若n=p^k(p为质数),φ(n)=p^k-p^(k-1). 证明：因为除了p的倍数外,其他数都跟n互质。
朴素算法实现：1.根据公式1：n=p1^k1*p2^k2*…pr^kr和公式2：φ(n)=n (1-1/p1) … (1-1/pr)。 2.可将公式2可拆成n* (1-1/p1)=n-n/p1计算。
int euler(int n) { int i,ans=n; for(i=2; i*i<=n; i++) if(n%i==0) { ans=ans-ans/i; while(n%i==0) n/=i;//把该素因子全部约掉 } if(n>1) ans=ans-ans/n; return ans; }例题1：poj2478 Farey
#include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int phi[1000005]; void solve() { memset(phi,0,sizeof(phi)); for (int i=2;i<=1000000;i++)//筛选求phi { if (!phi[i])//当phi[i]未访问 { for (int j=i;j<=1000000;j+=i) { if (phi[j]==0)//当phi[j]未访问 phi[j]=j-j/i;//算出phi[j]的个数(欧拉公式)。 } } } } int main() { int n; solve(); while (cin>>n) { if(n==0) break; long long sum = 0 ; for (int i=2;i<=n;i++) sum+=phi[i]; cout<<sum<<endl; } return 0; }例题2：poj3090 Visible Lattice Points escription 一个从(0,0)到(n,n)的坐标阵，如果(0,0)到(i,j)的连线被点挡住就算看不到,问多少点能被点(0,0)看到。 Input 输入T，代表接下来有T组数据，每组输入一个N，代表N*N的坐标阵。 Output 输出格式为：第几组 输入的数字N 可见点数个数 Sample Input Sample Output 4 2 1 2 5 4 2 4 13 5 3 5 21 231 4 231 32549 分析： 由图可知：左上和右下两部分具有对称性，我们考虑右下部分，对于点(x,y)： 1.有x>=y 2.若x和y不是互质的数(比如(4,2))，设t=gcd(x,y),必存在比它小的(x/t,y/t)与之重叠 (如(2,1))，那么(4,2)就为不可见点。
所以我们求的就是phi(y)(0
#include<iostream> #include<cstdio> #include<string.h> #include<algorithm> using namespace std; int phi[1010]; int n,sum; void fasteular() { memset(phi,0,sizeof(phi)); for(int i=2;i<=1010;i++) { if(!phi[i]) { for(int j=i;j<=1010;j+=i) { if(!phi[j]) phi[j]=j; phi[j]=phi[j]-phi[j]/i; } } } } int main() { fasteular(); int c,flag=1; cin>>c; while(c--) { cin>>n; sum=3; for(int i=2;i<=n;i++) { sum+=2*phi[i]; } cout<<flag++<<' '<<n<<' '<<sum<<endl; } return 0; }