● Smith numbers - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: huhaiming (一生只爱她), 信区: ACMICPC
标  题: Smith numbers
发信站: 荔园晨风BBS站 (Mon Apr 19 21:21:43 2004), 站内信件

#include <stdio.h>
#include <stdlib.h>

const int MAXP=10000,NUMP=10000;
int notprime[MAXP];
int primes[NUMP];
int numprimes;

int prime()
{
        int p,i,n;
        primes[0]=2;
        n=1;
        for (p=3; p<MAXP; p+=2) {
                if (!notprime[p]) {
                        for (i=2*p; i<MAXP; i+=p)
                                notprime[i]=1;
                        primes[n++]=p;
                }
        }
        return n;
}

int sumdigits(int a)
{
        int s;
        s = 0;
        while (a>0) {
                s += a%10;
                a = a/10;
        }
        return s;
}

int main()
{
        int N;
        int i,n,m;
        int s1,s2;

        freopen("D.in","r",stdin);
        freopen("D.out","w",stdout);

        scanf("%d",&N);
        numprimes=prime();
        while (N-->0 && scanf("%d",&n)==1) {
                n++;
                for (;;) {
                        m=n;
                        s1 = sumdigits(m);
                        s2=0;
                        for (i=0; i<numprimes && primes[i]*primes[i]<=m; i++)
                        {
                                while (m%primes[i]==0)
                                {
                                        s2+=sumdigits(primes[i]);
                                        m/=primes[i];
                                }
                        }
                        if (m!=n)
                        {
                                if (m>1)        s2+=sumdigits(m);
                                if (s1==s2)
                                {
                                        printf("%d\n",n);
                                        break;
                                }
                        }
                        n++;
                }
        }
        return 0;
}

--

菩提本无树，明镜亦非台

本来无一物，何处惹尘埃

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.202]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店