素数和合数

大家好，欢迎来到IT知识分享网。

本文无特殊说明，字母代表的都为整数

素数定义

n>1,n只有2个不同的约数(1,n)，则n为素数

合数定义

大于1的非素数的正整数

1不是素数也不是合数

性质

1.p为素数，p|ab，则a与b中至少一个数被p整除

2.p为合数，p|ab且(p,a)=1,则p|b

3.素数有无穷多个

证明

4.（标准分解）任何一个大于1的自然数 ，都可以唯一分解成有限个质数的乘积，n=(p1^a1)(p2^a2)….

证明

假设这个结论是错的，那么不满足这个结论的最小值为n，如果n为质数，n=n，与假设不符，而且n不是1，所以n为合数，但是合数可以写成2个小于n且大于1的数的积，即n=ab,1 < a <= b < n。由于n是不满足该结论的最小数，因此a和b都可以写成若干个质数的积，那么n当然也可以写成若干个质数的积，假设不成立，该结论正确。

筛法定义

通过一定方法得到一张表，可以查询一个数是否为质数

1.试除法

枚举2~sqrt(n)的所有数

inline bool check(int x){ for(int i = 2;i <= sqrt(x);i++){ if(!x%i) return 0; } return 1; }

2.埃氏筛

如果p是质数，那么2*p,3*p…都是合数

bool f[maxn]; vector<int>q; void find(int x){ f[0] = f[1] = 1; for(int i = 2;i <= x;i++){ if(!f[i]){ q.push_back(i); for(int k = i;k <= n / i;k++){ f[i * k] = 1; } } } }

线性筛

vector<int>q; int f[maxn];//f[i]为0，没有筛过，为i，是质数 void find(int x){ for(int i = 2;i <= x;i++){ if(!f[i]){ 
  //如果是质数 f[i] = i; q.push_back(i); } for(int k = 0;k < q.size();k++){ if(q[k] > f[i] || q[k] > n / i) break; f[i * q[k]] = q[k]; } } }

欧拉函数

1.若p为质数，则φ(p)=p-1

2.若i%p=0,φ(i*p)=p*φ(i)

3.若(i,p)=1,φ(i*p)=φ(i)*φ(p)

4.在性质3中，若p为质数，则φ(p*i)=φ(i)*(p-1)