不可摸数

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 5334    Accepted Submission(s): 1405

Problem Description

s(n)是正整数n的真因子之和，即小于n且整除n的因子和.例如s(12)=1+2+3+4+6=16.如果任何

数m，s(m)都不等于n,则称n为不可摸数.

 

 

Input

包含多组数据，首先输入T,表示有T组数据.每组数据1行给出n(2<=n<=1000)是整数。

 

 

Output

如果n是不可摸数，输出yes，否则输出no

 

 

Sample Input

3 2 5 8

 

 

Sample Output

yes yes no

 

1 /*  2 //代码一：-----超时  3 #include
       
          4 #include
        
           5   6 int fun(int num)  7 {  8     int i,k=0;  9     for(i=1;i<=(int)sqrt(num);++i) 10         if(num%i==0) 11         { 12             if(num/i!=i) 13             { 14                 k+=i; 15                 k+=num/i; 16             } 17             else 18                 k+=i; 19         } 20     return k; 21 } 22  23 int main() 24 { 25     int T,i,n,flag; 26     scanf("%d",&T); 27     while(T--) 28     { 29         flag=0; 30         scanf("%d",&n); 31         for(i=1;i<=(n-1)*(n-1);++i) 32         { 33             if(fun(i)==n) 34             { 35                 flag=1; 36                 break; 37             } 38         } 39         if(flag) 40             printf("no\n"); 41         else 42             printf("yes\n"); 43     } 44     return 0; 45 } 46  47  48  49 */ 50  51  52 /* 53 代码二：---AC 54 标准的筛选法---求出每个数的因子和， 55 然后看因子和是否在1000以内，是的话就证明等于因子和的这个数是不可摸数。 56 */ 57 #include
         
           58 #define MAX 500001   //这题数据求到这里就可以了 59  60 int sum[MAX]; 61 int flag[1001]; 62  63 void init()   //筛选法算出1000内存在的的因子和 64 { 65     int i,j; 66     for(i=1;i<=MAX/2;++i)  //不知道为啥 这里开到刚超出1000了就不对 67         for(j=i+i;j
          
           x/2; 99 2.     若x是一个正奇数，而s(x)是偶数，那么x必然是一个平方数。100 3.     只有一个不可摸数是奇数，那是5101 有以上三个结论，便可以算出一定范围内的不可摸数。102 103 代码三：104 */105 #include 
           
            106 using namespace std;107 int  arry[1005];108 109 void check()110 {111     int sum;112     for(int i=2;i<=2000;i+=2) 113     {114         sum=0;115         for(int j=1;j<=i/2;++j)116         {117             if(i%j==0)118                 sum+=j;119         }120         if(sum<=1000)121             arry[sum]=1;122     }123     for(int i=3;i<=1000;i+=2)124     {125         sum=0;126         for(int j=1;j<=(i*i)/2;j+=2)127         {128             if((i*i)%j==0)129                 sum+=j;130         }131         if(sum<=1000)132             arry[sum]=1;133     }134 135 }136 int main()137 {138     check();139     int t;140     scanf("%d",&t);141     while(t--)142     {143         int n;144         scanf("%d",&n);145         if(n==5)146             cout<<"yes"<