筛选法做题

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

int s[10000+1]; //值为1表示下标为 非寂寞数。值为0则表示下标为寂寞数。

int getjimo(int a)//返回a的d(n)数，所有的数都有d(n)数

{

     int sum=a;

     for( ; a>0; a=a/10)         sum+=a%10;            

     return sum;   

}

int main()

{

    int n;cin>>n;

    //对n以下的数字从1开始计算它的d(n)数

    for(int i=1;i<=n;i++){

           int dn=getjimo(i);

           //if(dn>n) break; //如dn数太大，会超出数组空间,超出n的数没有必要考虑，

           if(dn>n) continue; //开始用break只能打45分。

   //应该用continue，因为dn数与原始数的大小没有必然关系,即原数大，可能生成的dn却小 

           s[ dn  ]=1;

     }

     for(int i=1;i<=n;i++){

             if(s[i]==0) cout<<i<<endl;

       }

    return 0;

}