反質數問題,求不大于n的最大反質數

反質數：設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的一個約數，不要忘記)

 1 #include<iostream> 
 2 #include<cstring> 
 3 #include<cstdio> 
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 int p[]={2,3,5,7,11,13,17,19,23,29};
 9 
10 LL n, ans, cc;
11 
12 void dfs(int pos, int cnt, LL sum){
　　　　//pos，p數據的索引；cnt，約數的個數；sum，當前反質數的值
13     if(cnt > cc){
14         ans = sum;
15         cc = cnt;
16     }
17     if(cnt == cc && ans > sum)
18          ans = sum;
19     if(pos>=10) return;
20     for(int i=1; ; ++i){
21         sum*=p[pos];
22         if(sum > n) break;
23         dfs(pos+1, cnt*(i+1), sum);
24     }
25 }
26 
27 int main(){
28     cin>>n;
29     ans = 0;
30     dfs(0, 1, 1);
31     cout<<ans<<endl;
32     return 0;
33 }

轉載于:https://www.cnblogs.com/hujunzheng/p/4415544.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/531503.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/531503.shtml
英文地址，請注明出處：http://en.pswp.cn/news/531503.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！