数论基础 2025.2.10
1 .质数筛 是否为质数
质数-若一个正整数无法被除了1和它自身之外的任何自然数整除,则称该数为 质数(prime)
否则称该正整数为 合数(Composite number)
-
试除法(定义)
patr A bool Is_Prime(int x){ if(x<2) return 0; for(int i=2;i<=x-1;i++) if(x%i==0) return 0; return 1; } part B bool Is_Prime(int x){ if(x<2) return 0; for(int i=2;i*i<=x;i++) if(x%i==0) return 0; return 1; }
一个数
如果有因数,一定是一个大于
一个效应
或者就是
所以只要枚举1~
2.埃氏筛oioioioio
每个质数
的倍数
就是合数
bool Check[]; void Get_Prime(int n)//1~n{ for(int i=2;i<=n;i++) if(!Check[i]){ for(int j=2;i*j<=n;j++) Check[i*j]=1; } }
3 .线性筛
埃氏筛会重复标记 12—既是3的倍数也是2的倍数
所以线性筛!首先,任意一个合数都可以被分解成一个质数和一个数的积。对于任意一个合数,我们用“这个合数 = 最小质因数 × 最大因数(非自己)”,来表示
bool Is_Prime[]; int Prime[],top=0; void Get_Prime(int n){ for(int i=2;i<=n;i++){ if(!Is_Prime[i]) Prime[++top]=i; for(int j=1;i<=Prime[j]*i<=n&&j<=Top;j++){ Is_Prime[i*Prime[j]]=1; if(i%Prime[j]==0) break; } } }
2.欧拉函数(Euler's totient function)
欧拉
,若
的最大公因数为1,即
互质
就是1~n中与n互质的数的个数
将n分解质因数可得
-
[推导]
-
把
分解质因数后这些质因数在1~n中的倍数就是不能对
产生贡献的数,举个粒子:
那么在
中 2 ,3 ,5 的倍数就无法与300互质1-300中有
个2的倍数,有
个3的倍数,有
个5的倍数
同理 6 既是2的倍数也是3的倍数
10 既是2的倍数也是5的倍数
15 既是5的倍数也是3的倍数
这些数每个被减了两遍所以要加回来
1-300中有
个6的倍数......
所以
这么多个数与300不互质
转化一下
然后因式分解
!
再来一个??
!!!
int Got_Phi(int x){//找x的欧拉值 int ans=x;//初始认为全与x互质 for(int i=2;i*i<=x;i++){ if(x%i==0){//i是x的因数 ans=ans*((i-1)/i);//如公式 while(x%i==0) x/=i;//把次方剔除 } } if(x>1) ans=ans*((x-1)/x);//x自己是质数 return ans; }