2015年4月17日 星期五

2015/04/17 ACM-ICPC LiveArchive 2247 - Prime Digital Roots

/* https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=248 */
#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;

bool is_prime[1000000];
int Ans[1000000];

inline void set()
{
    fill(is_prime, is_prime+1000000, true);
    is_prime[0] = is_prime[1] = false;

    for(int i = 2; i < 10000; i++)
    {
        if( !is_prime[i] ) continue;

        for(int j = i*i; j < 1000000; j += i)
            is_prime[j] = false;
    }
}

inline int sum(int x)
{
    int re = 0;
    while(x) re += x%10, x/=10;
    return re;
}

int main()
{
    set();

    for(int i = 1; i < 1000000; i++)
    {
        if( is_prime[i] ) Ans[i] = i;
        else if( i < 10 ) Ans[i] = -1;
        else
        {
            int p = sum(i);
            Ans[i] = Ans[p];
        }
    }

    int x;
    while( scanf("%d", &x) )
    {
        if( !x ) break;
        printf("% 7d", x);

        if( Ans[x] == -1 ) puts("    none");
        else printf("% 8d\n", Ans[x]);
    }
}

沒有留言:

張貼留言