文章目录
数论1. 质数质数的判定---试除法分解质因数---试除法筛质数朴素筛法埃氏筛法线性筛法数论
1. 质数
质数：在大于1的整数中，如果只包含1和它本身这两个约数，那么这个数就称为质数。
判断质数最暴力的写法，按照质数的定义：看是否有其他的因子。
最朴素的暴力的时间复杂度O(n)
//时间复杂度O(n)bool isPrime(int n){if(n<2) return false;for(int i=2;i<n;i++)if(n%i==0) return false;return true;}
质数的判定—试除法
题目链接：Acwing866. 试除法判定质数
优化：枚举到n\sqrt{n}n，因为因数都是成对出现的，
如果d是n的因子，那么n/d也是n的因子，所以只需要枚举一部分就行，枚举哪一部分呢？就是d≤n/d 推出，d≤nd≤\sqrt{n}d≤n
这里n\sqrt{n}n的写法需要注意，这种调用数学函数n\sqrt{n}n的写法不好，太慢；另外写成i∗i≤ni*i≤ni∗i≤n存在溢出风险，最好的写法是i≤n/ii≤n/ii≤n/i
试除法求质数的时间复杂度O(n\sqrt{n}n)
//优化成O(根号n)bool isPrime(int n){if(n<2) return false;for(int i=2;i<=n/i;i++)if(n%i==0) return false;return true;}
分解质因数—试除法
题目链接：Acwing867. 分解质因数
暴力求质因数
下面i就是质因子，s是质因子i的阶数。
暴力的时间复杂度O(n)
void divide(int n){for(int i=2;i<=n;i++){if(n%i==0){//i一定是质数，因为下面n/=i,n一直在更新，如果是合数的话，已经被2除干净了int s=0;//统计质因子的阶数while(n%i==0){s++;n/=i;}cout<<i<<" "<<s<<endl;}}}
优化
给出一个重要性质：正整数n的因子中，最多包含1个大于n\sqrt{n}n的质因子。（可以用反证法来证明）
这里试除法的优化就是枚举到n\sqrt{n}n，然后剩下的1个大于n\sqrt{n}n的质因子单独处理，这样试除法分解质因数的时间复杂度O(n\sqrt{n}n)
ac代码
#include<bits/stdc++.h>using namespace std;//试除法分解质因数void divide(int n){//处理≤sqrt(n)的质因子for(int i=2;i<=n/i;i++){if(n%i==0){int s=0;while(n%i==0){s++;n/=i;}cout<<i<<" "<<s<<endl;}}//单独处理大于sqrt(n)的质因子if(n>1) cout<<n<<" "<<1<<endl;}int main(){int n;cin>>n;int tmp;for(int i=0;i<n;i++){cin>>tmp;divide(tmp);cout<<endl;}}
筛质数
题目链接acwing868. 筛质数
朴素筛法
朴素筛法的思想：从小到大枚举所有数，每次删掉该数的所有倍数，比如枚举到2，就删掉所有2的倍数。枚举到3，就删掉所有3的倍数。
需要用到prime数组，用来存放所有的质数；st数组，用来记录是否是某个数的倍数，即判断哪些是质数。需要count1变量，来存储质数的个数。
遍历的时候，需要考虑等号取不取。
朴素筛法的时间复杂度O(n×logn)O(n\times logn)O(n×logn)
#include<bits/stdc++.h>using namespace std;const int maxn=1000010;int prime[maxn];//prime数组存的是从小到大的质数int count1=0; //质数的个数bool st[maxn]; //判断是否是质数//朴素的筛法void primeNumber(int n){for(int i=2;i<=n;i++){if(!st[i]){//i不是别人的倍数，那么就是质数prime[count1++]=i;}for(int j=i+i;j<=n;j+=i) st[j]=true;//倍数筛掉}cout<<count1<<endl;}int main(){int n;cin>>n;primeNumber(n);return 0;}
埃氏筛法
优化：不需要筛掉所有数的倍数（合数的倍数一定不是质数，不用管），只需要筛掉质数的倍数，(因为质数的倍数是合数)。
//优化的筛法void primeNumber1(int n){for(int i=2;i<=n;i++){if(!st[i]){//i不是别人的倍数，那么就是质数prime[count1++]=i;for(int j=i+i;j<=n;j+=i) st[j]=true;//质数的倍数筛掉} }cout<<count1<<endl;}
有质数定理：当n很大时，1~n中有nlnn\frac{n}{lnn}lnnn个质数。
优化的筛法（埃氏筛法）时间复杂度O(n×loglogn)O(n\times loglogn)O(n×loglogn)，可以粗略地看成是O(n)。
两次提交结果
线性筛法
先说效率，数量级在10^7时候，线性筛法比埃氏筛法快一倍大概。
线性筛法时间复杂度O(n)
线性筛法的核心：一个数k只会被k的最小质因子筛掉。
//线性筛法void primeNumber2(int n){for(int i=2;i<=n;i++){if(!st[i]) prime[count1++]=i;for(int j=0;prime[j]<=n/i;j++){st[prime[j]*i]=true;if(i % prime[j]==0) break; //prime[j]一定是i的最小质因子}}cout<<count1<<endl;}
补充
如何找到第一个大于100000的质数呢？
解答:就是使用试除法判断质数的方法，从100000开始遍历，使用标志flag，如果i不是质数，flag=false；如果i是质数，flag=true；然后判断flag如果等于true，就break跳出循环，输出i，即为大于100000的最小质数。
#include<bits/stdc++.h>using namespace std;const int maxn=100000;int main(){for(int i=maxn;;i++){bool flag=true;for(int j=2;j<=i/j;j++){if(i%j==0){flag=false;break;}}if(flag){cout<<i<<endl;break;}}}
