Prime Digital Roots (UVALive 2247, Regionals 2001 >> South Pacific)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 1000000

vector<int>prime;
bool status[MX+2];

void PrimeGenerate(int n)
{
    int sq=sqrt(n);
    for(int i=3; i<=sq; i+=2)
    {
        if(!status[i])
            for(int j=i*i; j<=n; j+=(i<<1))
                status[j]=true;
    }

    status[0]=status[1]=true;
    for(int i=4;i<=n;i+=2) status[i]=true;

    /*prime.push_back(2);
    for(int i=3; i<=n; i+=2)
        if(!status[i])
            prime.push_back(i);*/
return;
}

int digitSum(int n)
{
    int ret=0;
    while(n)
    {
        ret+=n%10;
        n/=10;
    }
return ret;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n;
    PrimeGenerate(1000000);
    string s;
    char ch;
    while(cin>>n && n)
    {
        int origin=n;
        while(status[n])
        {
            int nn=digitSum(n);
            if(nn==n) break;
            n=nn;
        }
        if(!status[n])  cout<<setw(7)<< origin <<" "<<setw(7)<<n<<"\n";
        else  cout<<setw(7)<< origin <<" "<<setw(7)<<"none"<<"\n";
    }
return 0;
}