1333.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 54 行

#include<stdio.h>
#include<math.h>
int prime[10001];
int isprime(int n){
    int t=sqrt(1.0*n);
    for(int i=2;i<=t;i++)
        if(n%i==0)  return 0;
    return 1;
}
int rush(int n){
    int sum=0;
    while(n){
        sum+=n%10;
        n/=10;
    }
    return sum;
}
int smith(int n){
    int sum=0,j=0;
    int temp=n;
    while(true){
        if(n%prime[j]==0){
            n/=prime[j];
            sum+=rush(prime[j]);
            if(isprime(n)){
                sum+=rush(n);
                break;
                
            }
        }
        else
            j++;
    }
    return sum==rush(temp);
}
int main()
{
    int i,k,n;
    for(k=0,i=2;k<10001;i++)
        if(isprime(i))
            prime[k++]=i;
    while(scanf("%d",&n)!=EOF&&n){
        for(i=n+1;;i++){
            if(isprime(i))
                continue;
            if(smith(i)){
                printf("%d\n",i);
                break;
            }
        }
    }
    return 0;
}