反质数 C++问题

发布网友发布时间：2022-08-02 10:13

共1个回答

热心网友时间：2024-12-04 11:25

#include<iostream>
#include<algorithm>
#define bint long long
using namespace std;
const int N = 2000000001;// 2^30 = 1073741824
int prm[]={2,3,5,7,11,13,17,19,23,27};//连乘得：6023507490

struct nd {int v,m;}tmp[2000];// 备选数字、其约数个数
bool cmp(nd a,nd b){return (a.v==b.v?a.m<b.m:a.v<b.v);}

int ans[1000],ans_top,top =-1;

// k 当前正在使用prm[k]扩展
// lim 可乘次数的* ti+1必须<=ti
// d_num 当前val的约数个数
// val 当前得到的数字
void getAry(int k,int lim,int d_num,bint val)
{
if(lim==0||k==9){tmp[++top].v=val; tmp[top].m=d_num; return;}

int i = 0;// 选用prm[k]的次数，下一次作为lim传给后代
while(i<=lim && val<N)
{
getAry(k+1,i,d_num*(i+1),val);// 约数个数修正
i++;
val *= prm[k];
}
}

void getAns()
{
int maxm = -1;
top = ans_top = -1;
getAry(0,30,1,1); // 生成备选序列
sort(tmp,tmp+top+1,cmp); // 先数字大小再约数多少,从小到大排

for(int i=0;i<=top;i++)// maxm记录当前得到的最大约数个数
{
if(tmp[i].m > maxm)// 超过maxm，说明是一个antiprime
ans[++ans_top] = tmp[i].v;
if(tmp[i].m>maxm)
maxm=tmp[i].m;
}
}

int main(){
//freopen("antiPrm.out","w",stdout);
getAns();
//for(int i=0;i<=ans_top;i++)
// cout<<ans[i]<<endl;
int m,n;
//printf("Input M and N: ");
while (scanf("%d,%d", &m, &n) != EOF) {
if(m>n) {
int temp = m;
m = n;
n = temp;
}
int count = 0;
for (int i=0; i<=ans_top; i++) {
if (ans[i] >=m && ans[i]<=n) {
count ++;
if (count == 1)
printf("%d", ans[i]);
else printf(",%d", ans[i]);
}
}
if (count == 0) printf("NO\n");
else printf("\n");
}
return 0;
}