作者tropical72 (蓝影)
站内Prob_Solve
标题[请益] 判断完全数 - 改善效率 (已解决)
时间Mon Jul 11 22:35:26 2011
[题目]
对一个正整数 N 而言，将它除了本身以外所有的因数加起来的总和为 S，
如果 S>N，则 N 为盈数，如果 S<N，则 N 为亏数，
而如果 S=N，则 N 为完全数(Perfect Number)。
[solve]
一般人可能会这麽做：
for(sum=1, i=2; i!=N; ++i)
if(N%i==0) sum+=i;
但我觉得效率很差，於是想了一下。
假设，N % i ==0 ，那一定可以表达成 i*j=N, 得到 j=N/i，
这样下来，只要判断到 sqrt(N) 即可，唯一要小心的是，
若 i*i = N 时，就不用再求 j , 基於此思考程式码大致如下
int x, i, end, sum;
while(scanf("%d", &x)!=EOF){
if(x==1) {
puts("亏数");
continue;
}
sum=1, end = (int)ceil(sqrt(x));
for(i=2; i!=end; ++i)
if(x%i==0) sum+=i, sum+=(x/i);
// if(x%end==0) sum+=end;
if(end*end==x) sum+=end;
if(sum>x) puts("盈数");
else if(sum==x) puts("完全数");
else puts("亏数");
}
但拿这个去 run, 不是正确的, 想请教一下，是我的逻辑有问题，
还是我的码有问题？ 谢谢各位。
--
YouLoveMe() ? LetItBe() : LetMeFree();
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 180.177.73.222
※ tropical72:转录至看板 C_and_CPP 07/11 22:45
1F：→ tkcn:没仔细看，不过 x==1 的处理是错的 07/11 22:53
2F：→ firejox:是因为1不是质数吗? 07/11 22:56
3F：→ tkcn:"将它除了本身以外所有的因数" 07/11 22:58
4F：→ tropical72:我再改过我修过的部份, 目前仍有误 XD 07/11 22:59
※ 编辑: tropical72 来自: 180.177.73.222 (07/11 22:59)
5F：→ firejox:x*x==end .... 07/11 23:02
6F：→ tropical72:对不起楼上, 是我 key 错 XD 07/11 23:03
※ 编辑: tropical72 来自: 180.177.73.222 (07/11 23:03)
※ 编辑: tropical72 来自: 180.177.73.222 (07/11 23:07)
7F：→ tkcn:x 减掉 EPS 再做 sqrt 试试? (int)ceil(sqrt(x-EPS)) 07/11 23:07
8F：→ tropical72:谢谢tkcn,这支程式码已 AC, 非常感谢您的指导 *^_^* 07/11 23:14