一、质数：

定义：若一个正整数无法被除了1和它自身之外的任何自然数整除，则称该书为质数，否则该正整数为合数。

对于一个足够大的整数N，不超过N的质数大约有N / lnN 个，即每lnN个数中大约有1个质数。

1、质数判定：

1】试除法：

若一个正整数n是合数，则存在一个小于等于sqrt（n）的数能整除n。其实也好理解，一个合数的因子总是成对出现，比如10的因子就有（1，10）、（2，5）。所以，小于sqrt（n）的范围内必然存在较小的那一个因子。用这个判断素数就是判断是否存在因子。也可以用来枚举因子数。

bool is_prime(int n) { for(int i=2;i<=sqrt(n);i++) { if(n%i==0) return false; } return true; }

试除法枚举求算因子个数

int factor(int n) { int cnt=0; for(int i=1;i<=sqrt(n);i++) { if(n%i==0) { cnt++; if(i*i!=n) cnt++; } } return cnt; }

2】miller rabin质数测试：

在这里先不做探讨，只给出模板

#include<bits/stdc++.h> #define LL long long using namespace std; inline int read() { char c=getchar(); int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*f; } int N,M,Test[10]={2,3,5,7,11,13,17}; LL pow(int a,int p,int mod) { int base=1; for(;p;p>>=1,a=(1LL*a*a)%mod) if(p&1)base=(1LL*base*a)%mod; return base % mod; } bool Query(int P) { if(P==1)return 0; int t=P-1,k=0; while(!(t&1))k++,t>>=1; for(int i=0;i<4;i++) { if(P==Test[i])return 1; LL a=pow(Test[i],t,P),next=a; for(int j=1;j<=k;j++) { next=(a*a)%P; if(next==1&&a!=1&&a!=P-1)return 0;//a=p-1就代表a是最后一个，就不存在next了 a=next; }//二次探测定理判断 if(a!=1)return 0;//费马小定理 } return 1; } int main() { N=read();M=read(); while(M--) {if(Query(read()))printf("Yes\n"); else printf("No\n");} }

3】用java，其实这个只能是一个知识积累吧

import java.util.*; import java.math.*; public class TEST { public static void main(String args[]){ Scanner cin = new Scanner(System.in); while(cin.hasNext()){ BigInteger m = cin.nextBigInteger(); if(m.isProbablePrime(1)){ System.out.println("Yes"); } else{ System.out.println("No"); } } } }

2、质数的筛选

1】埃氏筛法（接近线性）

思想就是：如果x是素数，那么x的所有倍数就不是素数。这个函数关键的地方就是标记倍数。下面的代码对这个筛法进行了优化，即从x平方开始筛素数。从2开始遍历，对于每个质数都暴力算出它的所有倍数并筛掉，详见下面的代码实现。

void primes(int n) { memset(v,0,sizeof v); for(int i=2;i<=n;i++) { if(v[i]) continue; cout<<i<<endl; for(int j=i;j<=n/i;j++) v[i*j]=1; } }

2】线性筛法

即使再优化后，埃氏筛法仍然存在重复标记合数，例如12既会被2又会被3标记，在标记2的倍数时，12=6*2，在标记3的倍数时，12=3*4，其根本原因是我们没有确定出唯一的产生12的方式。我们在生成一个需要标记的合数时，每次只向现有的数中乘上一个质因子，并且让它是这个合数的最小质因子

v数组记录每个数的最小质因子

 每个合数都一定可以表示为一个素因子和另一个数相乘的形式，而每个素数的所有在N范围内的倍数的数都被筛了，即所有1到N范围内的合数都被筛掉了。我们可以做到让合数x只被它的最小的素因子筛来实现 "线性" 

void primeN(int n) { memset(v,0,sizeof v); m=0;//记录素数的个数 for(int i=2;i<=n;i++) { if(v[i]==0){//表示i是素数 v[i]=i; prime[++m]=i; } for(int j=1;j<=m;j++) { if(prime[j]>v[i]||prime[j]>n/i) break;//如果在之前已经确定的素数里有大于i的最小素因子，则break v[i*prime[j]]=prime[j]; } } for(int i=1;i<=m;i++) cout<<prime[i]<<endl; }

3、质因数的分解

1】算数基本定理（***）

唯一分解

#include<iostream> #include<cstring> #include<cstdio> using namespace std; typedef long long ll; const int maxn=1e6+2; bool is[maxn]; int cnt =0; ll p[maxn], prim[maxn]; int k; void find_prim() { k = 0; for(ll i = 2; i <= maxn; i++) { if(!p[i]) { prim[k++] = i; for(ll j = i+i; j <= maxn; j+=i) { p[j] = 1; } } } } ll cont(ll a) { ll s = 1; if(a == 0) { return 0; } ll tt = 0; ll i = 0; while(prim[i] < a && i < k) { tt = 0; if(a%prim[i] == 0) { while(a%prim[i] == 0) { a/=prim[i]; tt++; } } s *= tt+1; i++; } if(a > 1) { s *= 1+1;//一次 } return s; } void divide(int n) { m=0; for(int i=2;i<=sqrt(n);i++) { if(n%i==0){ p[++m]=i,c[m]=0; while(n%i==0) n/=i,c[m]++; } } if(n>1) p[++m]=n,c[m]=1; for(int i=1;i<=m;i++) cout<<p[i]<<" "<<c[i]; }

二、约数 

n是d的倍数，记为d|n

1】算数基本定理的推论

在算数基本定理中，若正整数N被唯一分解为N=p1^c1*p2^c2....pm^cm

N的正约数个数为（c1+1）*（c2+1）*...*(cm+1)

N的所有正约数的和为（1+p1+p1^2+p1^3+...+p1^c1）*...*

关于试除法求N的正约数集合已经在前面【质数判定】介绍

关于试除法也有推论：一个整数N的约数个数上界为2 

求1~N每个数的正约数集合可以使用倍数法：

vector<int> factor[500010]; for(int i=1;i<=n;i++) for(int j=1;j<=n/i;j++) factor[i*j].push_back(i); for(int i=1;i<=n;i++){ for(int j=0;j<factor[i].size();j++) printf("%d ",factor[i][j]); puts(""); }

2】最小公倍数与最大公约数

二者联系：

gcd(a,b)*lcm(a,b)==a*b

 

1、更相减损术：

任意a，b∈N，a>=b,有gcd（a,b）==gcd(b,a-b)=gcd(a,a-b); 任意a，b∈N，a>=b,有gcd(2a，2b)==2gcd(a,b)

2、欧几里得算法

int gcd(int a,int b) { return b?gcd(b,a%b):a; }

 

3】互质与欧拉函数函数

互质：任意a,b∈N，若gcd(a,b)==1,则称a，b互质。

欧拉函数：1~N中与N互质的个数成为欧拉函数，记为φ（N）

求n的欧拉函数：

inline ll phii (ll n){ if(n==1)return 0; int ans=n; for(int i=2;i<=n;i++){ if(n%i==0){ ans=ans/i*(i-1); while(n%i==0)n/=i; } } if(n>1)ans/n*(n-1); return ans; }

 

欧拉函数线性筛法：

inline void primes_euler (ll n){ memset(v,0,sizeof(v)); m=0; for(int i=2;i<=n;i++){ if(v[i]==0){ v[i]=i; prime[++m]=i; phi[i]=i-1; } for(int j=1;j<=m;j++){ if(prime[j]>v[i]||prime[j]>n/i)break; v[i*prime[j]]=prime[j]; phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]); } } }

 

欧拉函数的性质：

1、对于一个质数n，φ（n）= n - 1

2、φ（p^a）=p^a-p^(a-1)

3、φ(n*m)=φ(n)*φ(m)   当gcd(n,m)=1时

4、1~n中与n互质的数的和为n * φ（n）/  2

5、

 

6.当n是奇数时  φ(2*n)=φ(n)

7、当n>2时   φ(n) mod 2=0

三、同余

1】若整数a和整数b除以正整数m的余数相等，则称a，b模m同余，记为ab（mod m）

2】费马小定理：若p是质数，则对与任意整数a，有a^p=a(mod p)

3】欧拉定理：若正整数a，n互质，则a^φ（n）=1(mod n)

欧拉定理的推论：若正整数a，n互质，则对于任意正整数b，有a^b=a^(b mod φ（n)) (mod n）

引理：若正整数a，n互质，则满足a^x=1(mod n)的最小正整数x0是φ(n)的约数。

4】扩展欧几里得算法

对于任意整数a，b，存在一对整数x，y，满足ax+by=gcd（a，b）;

inline ll exgcd (ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } ll d=exgcd(b,a%b,x,y); ll z=x; x=y; y=z-(a/b)*y; return d; }