数论
Date:2023.1.14
素数(质数)
定义
只有两个因数的数叫做质因数(1和它本身)
既不是素数也不是合数
判断素数
朴素算法
枚举 的所有数字,判断其是否能被整除,时间复杂度:
或者可以优化一下,枚举区间改成 ,时间复杂度:
埃式筛法
对于多个大数,朴素算法显然慢了
对于求多个质数,我们可以运用标记思想
我们知道,对于一个 ,它的倍数一定是约数
所以我们可以从小到大的枚举 内的质数,标记它的倍数,没被标的即是质数
时间复杂度:(表示)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| #include<stdio.h> #include<cmath> #define N 10005 using namespace std; int n; int f[N],ss[N],cnt; void ssai(int x){ for(register int i=2;i<=x;i++){ if(!f[i]) ss[++cnt]=i; for(register int j=2;j<=n;j++){ if(ss[cnt]*j>n) break; f[ss[cnt]*j]=1; } } } int main(){ scanf("%d",&n); ssai(n); for(int i=1;i<=cnt;i++) printf("%d\n",ss[i]); system("pause"); }
|
欧拉筛法(线性筛法)
我们回忆一下埃式筛法,对于一个约数,它可能被多个素数标记,浪费了时间
那么欧拉筛法就只让一个约数被他最小的质因子标记
时间复杂度:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| #include<stdio.h> #include<cmath> #define N 10005 using namespace std; int n; int f[N],ss[N],cnt; void ssou(int x){ for(register int i=2;i<=n;i++){ if(!f[i]) ss[++cnt]=i; for(register int j=1;j<=cnt;j++){ if(ss[j]*i>n) break; f[i*ss[j]]=1; if(i%ss[j]==0) break; } } } int main(){ scanf("%d",&n); ssou(n); for(int i=1;i<=cnt;i++) printf("%d\n",ss[i]); system("pause"); }
|
注意,以上两个筛法都是求中的素数
分解质因数
这还不简单
算数基本定理(唯一分解定理):任何一个约数都可以被分解成几个素数相乘的形式
根据这条定理,我们可以采用试除法
从 枚举 的质数 ,遇到素数就一直除以它,直到不能整除为止,并记录除的次数
最后若,也要算一个素数
时间复杂度:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| #include<stdio.h> #include<math.h> using namespace std; int n; int dpf(int x){ int sum=0; for(int i=2;i<=sqrt(x);i++) while(x%i==0){ x/=i; sum++; } if(x>1) sum++; return sum; } int main(){ scanf("%d",&n); int ans=dpf(n); printf("%d",ans); return 0; }
|
合数
合数,通俗理解:不是素数的正整数就是合数(1 除外)
定义
除了 1 和它本身之外还有其他因数的数叫合数
1 既不是素数也不是合数
判断合数
应该没有这种题吧
先用欧拉筛法,加个标记,没被标的即使合数
这么简单,不用放代码吧
求约数个数
约约数个数定理:对于一个大于 1 的正整数可以 分解质因数:
则 1 的约数个数为:
这里给出证明:
由约数的定义可得:有这些约数,共有个
同理,有个约数,有个约数
中有个因子,中有个因子
乘法原理可得:
时间复杂度:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| #include<stdio.h> #include<math.h> using namespace std; int n; int dpf(int x){ int cnt=0,sum=1; for(int i=2;i<=sqrt(x);i++){ while(x%i==0){ x/=i; cnt++; } sum*=(cnt+1); } if(x>1) sum*=2; return sum; } int main(){ scanf("%d",&n); int ans=dpf(n); printf("%d",ans); return 0; }
|
如果你要求所有约数,用质因数一个个乘吧
时间复杂度:
公约数&公倍数
公约数
定义
若 x 同时是 a 和 b 的约数,则称 x 是 a 与 b 的公约数
公倍数
定义
若 a 和 b 同时是 x 的约数,则称 x 是 a 与 b 的公倍数
最大公约数
定义
若 x 是 a 和 b 的公约数且 x 最大,则称 x 是 a 和 b 的最大公约数
求最大公约数
证明:
设 ,则
设 ,则
反过来,
设
则
移项得:
显然,
,即
得证
时间复杂度:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| #include<stdio.h> #include<math.h> using namespace std; int a,b; int gcd(int x,int y){ if(!b) return a; return gcd(b,a%b); } int main(){ scanf("%d%d",&a,&b); int ans=gcd(a,b); printf("%d",ans); return 0; }
|
补充
若 ,我们称这两个数 互质
即最大的公约数为 1
最小公倍数
定义
若 x 是 a 和 b 的公倍数且 x 最小,则称 x 是 a 和 b 的最小公倍数
求最小公倍数
证明:
设
则
时间复杂度:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| #include<stdio.h> #include<math.h> using namespace std; int a,b; int gcd(int x,int y){ if(!b) return a; return gcd(b,a%b); } int main(){ scanf("%d%d",&a,&b); int ans=gcd(a,b); printf("%d",a*b/ans); return 0; }
|
欧拉函数
定义
欧拉函数,即 ,表示小于等于 n 且与 n 互质数的个数
即
性质
积性函数
逆元