反质数问题,求不大于n的最大反质数

时间:2023-01-20 20:15:21
反质数:设f(n)表示n个约数的个数,如果对于任意x有0<x<n, f(x) < f(n),那么n就是一个反质数
我们都知道对于任意一个数n,都可以用质数乘积的形式表示出来:x = p1^k1+p2^k2...pn^kn 一个数n如果可以表示成 n = p1^k1 + p2^k2, 那么它的约数的个数就是 (k1+1)*(k2+1) ::k1个p1,可以产生k1个约数,分别是p1^1, p1^2...p1^k1, 同理k2个p2
那么这k1个约数与k2个约数分别相乘,又会得到k1*k2个约数
总的约数的个数就是 k1*k2+k1+k2+1(还有就是1,也是n的一个约数,不要忘记)
 #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std; typedef long long LL;
int p[]={,,,,,,,,,}; LL n, ans, cc; void dfs(int pos, int cnt, LL sum){
    //pos,p数据的索引;cnt,约数的个数;sum,当前反质数的值
if(cnt > cc){
ans = sum;
cc = cnt;
}
if(cnt == cc && ans > sum)
ans = sum;
if(pos>=) return;
for(int i=; ; ++i){
sum*=p[pos];
if(sum > n) break;
dfs(pos+, cnt*(i+), sum);
}
} int main(){
cin>>n;
ans = ;
dfs(, , );
cout<<ans<<endl;
return ;
}