分解质因数
Smith Numbers http://poj.org/problem?id=1142 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=133
1 #include<cstdio> 2 int fac[128]; 3 int find_fac(int n){//对n分解质因数，返回质因数个数 4 int cnt=0; 5 for(int i=2;i*i<=n;i+=2){ 6 while(!(n%i)){ 7 n/=i; 8 fac[cnt++]=i; 9 } 10 if(i==2) i--; 11 } 12 if(n>1) fac[cnt++]=n; 13 return cnt; 14 } 15 int div(int x){ 16 int res=0; 17 while(x){ 18 res+=x%10; 19 x/=10; 20 } 21 return res; 22 } 23 bool judge(int n){ 24 int lf=find_fac(n); 25 if(lf==1) return false; 26 int sum=0; 27 for(int i=0;i<lf;i++){ 28 sum+=div(fac[i]); 29 } 30 if(sum==div(n)) return true; 31 return false; 32 } 33 int main(){ 34 int n; 35 while(~scanf("%d",&n),n){ 36 while(!judge(++n)); 37 printf("%d ",n); 38 } 39 return 0; 40 }
Perfection http://poj.org/problem?id=1528
求所有除数的和
1 #include<cstdio> 2 int ds_func(int n){//求n所有除数的和 3 int ret=1,m=n,t; 4 for(int i=2;i*i<=n;i+=(i==2)?1:2){ 5 if(!(n%i)){ 6 t=i*i; 7 n/=i; 8 while(!(n%i)){ 9 t*=i; 10 n/=i; 11 } 12 ret*=(t-1)/(i-1); 13 } 14 } 15 return n>1?ret*(n+1):ret; 16 } 17 int main() { 18 int n; 19 puts("PERFECTION OUTPUT"); 20 while(~scanf("%d",&n),n){ 21 printf("%5d",n); 22 int sum=ds_func(n); 23 if(sum>n+n) puts(" ABUNDANT"); 24 else if(sum==n+n) puts(" PERFECT"); 25 else puts(" DEFICIENT"); 26 } 27 puts("END OF OUTPUT"); 28 return 0; 29 }