不可摸数

题目意思：

s(n)是正整数n的真因子之和，即小于n且整除n的因子和.例如s(12)=1+2+3+4+6=16.如果任何
数m，s(m)都不等于n,则称n为不可摸数.
解题思路：通过质因数分解求因子和

结论：1000以内的奇数都是可摸的 除5以外

     偶数只要算到n*2

     奇数算到 n*n

code:

#include
const int size=1005;
int x[size],prime[5000];
//计算<=M的素数
void PRIME(int M)
{int i,j,k;
prime[1]=2;
prime[2]=3;
k=2;
for(i=5;i<=M;i+=2)
{
for(j=2;prime[j]*prime[j]<=i;j++)
{
if(i%prime[j]==0)goto loop;
}
k++;prime[k]=i;
loop:;
}
prime[0]=k;
}

//因子和(含n,6的因子和是1+2+3+6)
int sum(int n)
{int i,j,s,t,k,p;
k=1;
for(i=1;i<=prime[0];i++)
{
s=1;p=prime[i];
while(n%prime[i]==0){s+=p;p*=prime[i];n/=prime[i];}
if(s>1)k*=s;
if(n==1)break;
if(n/prime[i]}
return k;
}

int main()
{
    int i,temp,cas,n;
    PRIME(10000);
    for(i=1;i<=1000;i++)x[i]=0;
   
    //偶数的时候 n*2
    for(i=2;i<=2000;i+=2)
    {
    temp=sum(i)-i;
    if(temp<=1000)x[temp]++;                   
    }   
    //奇数 n*n
    for(i=3;i<=1000;i+=2)
    {
    temp=sum(i*i)-i*i;
    if(temp<=1000)x[temp]++;                    
    }
   
    int count=0;
 for(i=1;i<=1000;i++)
 if(x[i]==0&&i%2==0||i==5) {printf("%d\n",i);count++;x[i]=0;}
 else x[i]=1;
 printf("%d\n",count);
   
       
    scanf("%d",&cas);
    while(cas--)
    {
    scanf("%d",&n);
    if(x[n]==0) printf("yes\n");
    else printf("no\n");           
    }
}
/*
1000以内不可模数 89个
2
5
52
88
96
120
124
146
162
188
206
210
216
238
246
248
262
268
276
288
290
292
304
306
322
324
326
336
342
372
406
408
426
430
448
472
474
498
516
518
520
530
540
552
556
562
576
584
612
624
626
628
658
668
670
708
714
718
726
732
738
748
750
756
766
768
782
784
792
802
804
818
836
848
852
872
892
894
896
898
902
926
934
936
964
966
976
982
996
*/