zoj 2562

求反素数

搜索剪枝即可

#include<stdio.h>
typedef long long ll;
int yes[200];
int prime[100];
ll maxsum,minnum,n;
void dfs(ll num,ll sum,int pos,int limit){
    int i;
    ll temp;
    if(sum>maxsum){
        minnum=num;
        maxsum=sum;
    }
    if(sum==maxsum)
        if(num<minnum)
            minnum=num;
    temp=num;
    for(i=1;i<=limit;i++){
        temp=temp*prime[pos];
        if(temp>n)
            break;
        dfs(temp,sum*(i+1),pos+1,i);
    }
}
int main(){
    int i,j;
    for(i=2;i<=10;i++){
        if(!yes[i])
            for(j=i*i;j<=100;j+=i)
                yes[j]=1;
    }
    j=1;
    for(i=2;i<=50;i++)
        if(!yes[i])
            prime[j++]=i;
    while(scanf("%lld",&n)==1){
        maxsum=0;
        minnum=1;
        dfs(1,1,1,50);
        printf("%lld\n",minnum);
    }
    return 0;
}