PersonalCorpus 版 (精华区)

1247919 Big Guava ... 10042 Accepted
0:00.473 420 2002/11/19 06:09:27.221

 int prime[5001];

void makeprime(int n)
{

    int i,j,k,l;
    bool ok;

    prime[0]=2; k=1;
    for (i=3; k<n;i+=2) {
        l=sqrt(i); ok=true;
        for (j=0;j<k,prime[j]<=l;j++) if (i%prime[j]==0) {
            ok=false; break;
        }
        if (ok) prime[k++]=i;
    }
}


void main()
{
#ifndef ONLINE_JUDGE
    freopen("k:\\uva\\i10042","r",stdin);
    freopen("k:\\uva\\o10042","w",stdout);
#endif

    int i,j,k,l,t,n,a,b;

    makeprime(4792);

    scanf("%d",&t);
    while (t--) {
        scanf("%d",&n);
        while (1) {
            n++;
            i=n; a=0;
            while (i>0) {
                a+=i%10;
                i/=10;
            }
            i=n; b=0; l=0;
            for (k=0;(k<4792)&&(i>1);k++) while (i%prime[k]==0) {
                j=prime[k]; l++;
                while (j>0) {
                    b+=j%10;
                    j/=10;
                }
                i/=prime[k];
            }
            if (l==0) continue;
            if ((l==1)&&(i==1)) continue;
            if (i>1) while (i>0) {
                b+=i%10;
                i/=10;
            }
            if (a==b) break;
        }
        printf("%d\n",n);
    }
}