【数论】素数
目录
素数判定
试除法
分解质因数
试除法
质数筛
埃式筛法
线性筛法（欧拉筛）
约数
试除法求约数
约数个数
其它结论
质数定理
反素数
素数判定
试除法
时间复杂度：O(sqrt(n))
核心：从小到大枚举，优化：n能整除d，n一定能整除n/d
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;
}
提示：关于判断条件的写法，还可写作i*i<=n(但有溢出风险)，i<=sqrt(n)（sqrt执行速度慢)
分解质因数
试除法
时间复杂度：最坏O(sqrt(n)) 最好O(logn)
核心：从小到大枚举。优化：由于n中最多只会包含一个大于sqrt(n)的质因子，只需要单独处理大于sqrt(n)的
void divide(int n){
for (int i=2;i<=n/i;i++){
// 当枚举到i时，n已经将2~i-1都除尽了，所以i一定没有2~i-1的因子，i一定是个质数
if (n%i==0){
while(n%i==0){
n/=i;
}
cout< } } if(n>1) cout< } 质数筛 埃式筛法 时间复杂度：O(nloglogn) 核心：把区间内每一个数的所有倍数删掉，所有剩下的数都是质数 优化：由于合数的倍数会被质数的倍数所覆盖，所以我们只需要删除所有质数的倍数即可 int prime[N],cnt; bool f[N]; void getPrime(int n){ for (int i=2;i<=n;i++){ if (!f[i]){ prime[cnt++]=i; for (int j=i+i;j<=n;j+=i) f[j]=true; } } } 线性筛法（欧拉筛） 时间复杂度：O(n) 核心：每一个数只会被它的最小质因子筛掉 1.i % pj == 0 :pj是从小到大枚举的质数，第一次出现i % pj == 0一定说明 pj 是 i 的最 小质因子 2.i % pj != 0:pj一定小于i的所有质因子，pj也一定是pj*i的最小质因子 int prime[N],cnt; bool f[N]; void getPrime(int n){ for (int i=2;i<=n;i++){ if (!f[i]) prime[cnt++]=i; for (int j=0;i*prime[j]<=n;j++){ f[prime[j]*i]=true; if (i%prime[j]==0) break; } } } 约数 试除法求约数 时间复杂度：O(sqrt(n)) 核心：直接枚举即可，注意要判断( i != n/i ) vector vector for(int i=1;i<=n/i;i++){ if(n%i==0){ res.push_back(i); if (i!=n/i) res.push_back(i); } } return res; } 约数个数 原理：对于任意一个数，我们对它进行质因数分解，它总能写成，而它的因数则可以通过改变质因数p1，p2，……，pn的指数来组合。比如我们将72进行质因数分解，得到，那么72的所有因数有统一的表达式。 那么约数的个数也就很好求了，就是x,y的排列组合（每个数能取0-ki）即 补充一些估计： 1~n中约有nlnn个约数、nlnn个素数 逆向思维，想1~n中有多少个倍数，1的倍数有n个，2的倍数有n/2个，3的倍数有n/3个……n的倍数有n/n个。总共的约数也就是，约为nlnn 1~n中约数最多有1536个 约数之和 公式： 很好理解，直接把结论展开，每个括号里任意取一个出来，组合起来，都是一个约数 反素数 素数是含有因子最少的，反素数就是含有因子最多的（因子个数相同时取最小的），所以反素数是相对于一个集合来说的。 标准定义：对于某个正整数x,如果任何小于x的正数的约数个数都小于x的约数个数，则称为是反素数。 反素数的问题大多都是直接的板子题。 常见的有：（1）给定因子个数，求反素数 . （2）求n以内的最大的反素数 解法： 上面我们已经介绍了约数个数定理。 我们可以再观察一下反素数的特点。 1.质因数p1，p2，……，pn应该是从2开始连续的。因为因数的个数只和质因数的指数相关，如果不是从2开始连续的（比如为，那么与它因数个数相同，而且更小，所对应的数才应该是反素数） 2.指数k1>=k2>=……>=kn，这个也很好理解，因为反素数要求约数最多的里面最小的，所以肯定要给小的数分配的幂指数更多一点。 发现了这两个规律后，我们的解法也就出现了，我们只需要去枚举底数和指数，将它们进行组合。简单计算一下，可以发现最差的情况，每一个幂次都是1，只需要15个质数相乘就能达到6e18。而指数，也同样考虑最差的情况，也就是2^64，最多达到64，所以时间复杂度是可以接受的。 模板 需要的参数：当前枚举的是第几个素数，上一个素数的指数，约数数量，当前的值 （1）给定因子个数，求反素数 #include using namespace std; using ll=long long; ll n; ll prime[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; ll res; void dfs(int k,int last,ll num,ll val){ if (num>n||k>=16) return ;//再乘一个一定会比n大 if (num==n&&val res=val; return ; } for (int i=1;i<=last;i++){//枚举prime[k]的指数 if (val*prime[k]>res) break; val*=prime[k]; dfs(k+1,i,num*(i+1),val); } } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; res=LLONG_MAX; dfs(0,63,1,1);//预先算一下2^x达到n cout< } （2）求n以内的最大反素数 对于1e18，要使用unsigned long long，以防溢出 #include using namespace std; using ll=unsigned long long; ll n; ll prime[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; ll res,maxd;//最大反素数的值，约数数量 void dfs(int k,int last,ll num,ll val){ if (val>res||k>=16) return ;//再乘一个一定会比n大 if (num>maxd||(num==maxd&&val res=val; maxd=num; } for (int i=1;i<=last;i++){//枚举prime[k]的指数 if (val*prime[k]>n) break; val*=prime[k]; dfs(k+1,i,num*(i+1),val); } } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; dfs(0,63,1,1);//预先算一下2^x达到n cout< }