大神的世界

跟建立質數表的概念相似

先假設小於1000000的數皆是self-number

接著從1開始

如果是self-number的話

就記錄起來

再按照題目的規則剃除

直到1000000

接著輸出即可

#include <iostream>
#include <cstring>

#define N 1000001

using namespace std;

bool bSelfNum[N];
int selfNum[N];
int self_ptr;

void setSelfNum()
{
    int i, curNum, nextNum;

    memset(bSelfNum, true, sizeof(bSelfNum));

    for(i = 1, self_ptr = 0; i<N; i++)
        if(bSelfNum[i])
        {
            selfNum[self_ptr++] = i;

            nextNum = i;
            while(nextNum < N)
            {
                curNum = nextNum;
                while(curNum > 0)
                {
                    nextNum += curNum%10;
                    curNum /= 10;
                }

                if(!bSelfNum[nextNum])
                    break;

                bSelfNum[nextNum] = false;
            }
        }
}

int main()
{
    setSelfNum();

    for(int i = 0; i < self_ptr; i++)
        cout << selfNum[i] << endl;
}