作者Strogatz ( )
看板C_and_CPP
标题Re: [问题] 小弟写了一个程式 就差了一点
时间Wed Aug 12 18:39:27 2009
小弟我也是个刚学C/C++的新手
看了这篇试着写了一下 请各位不吝指教!!^^
#include <stdio.h>
#include <stdlib.h>
int primetest(int);
int main()
{ int j(0),n;
printf("enter a number:");
scanf("%d",&n);
int a[n];
printf("N have factor(s):"); ┐
for(int i=1;i<=n;i++){ │这部分印出所有因数
if(n%i==0){ │
printf("%d\t",i); ┘
if(primetest(i)==0){ ┐
a[j]=i; │这部分把上面得到的因数做质因数测试
j++; │并将结果存进向量a[]
} ┘
}
}
printf("\n");
printf("N has prime(s):"); ┐
for(int i=1;i<j;i++){ │列印出质因数
printf("%d\t",a[i]); │
} ┘
printf("\n");
system("pause");
return 0;
}
int primetest(int p){ ┐
int counter(0); │
for(int i=2;i<=p/2;i++){ │
if(p%i==0) │质因数测试器
counter++; │
} │
return counter; │
} ┘
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.230.13.134
1F：→ Strogatz:我自觉这写法结果虽然是正确的 但效率非常低 0rz 08/12 18:41
2F：推 VictorTom:纯找小於N的质数的话, 有个常见的作法是 筛法 :) 08/12 18:46
3F：→ su31o4gj83:如果你要找质因数的话i不用跑完, 不过所有因数的话.... 08/12 18:55
4F：→ su31o4gj83:呵~我看到你的质因数测试器了 08/12 18:58
5F：→ su31o4gj83:其实所有的因数的话也不用跑完, 一半就可以了 08/12 19:01
6F：推 VictorTom:其实那是质数测试器, 只是因为喂给它的是因数....XD 08/12 19:10
7F：→ Strogatz:yes, 我本来是写n/2, 不过後来想到n本身也是因数,但是去 08/12 19:11
8F：→ VictorTom:话说不用跑一半啦, 跑根号p就够了:) 08/12 19:11
9F：→ Strogatz:掉 1/2 factor 又增加太多计算了 08/12 19:12
10F：→ Strogatz:是没错 不过我不知道有没有预设的sqrt() 没有的话要额外 08/12 19:13
11F：推 VictorTom:math.h有sqrt吧?? 还是得用pow(n,0.5)?? 有点忘了.... 08/12 19:14
12F：→ VictorTom:话说, 其实还是重复算很多, 这时候筛下去比较爽啦XD 08/12 19:15
13F：→ Strogatz:有 thanks 08/12 19:34
14F：→ su31o4gj83:另外, 可以考虑移除primetest, 直接放到main的for loop 08/12 20:37
15F：→ su31o4gj83:跑一半我是想说/2比sqrt省, 不过应该还是用sqrt比较好 08/12 20:41
16F：→ su31o4gj83:毕竟数字大一点, 用sqrt可少跑很多步 08/12 20:43
17F：→ su31o4gj83:我是觉得有时候程式好读比效能重要XD 08/12 20:48
18F：→ Strogatz:哈 我写的太挤了 08/12 21:39
19F：→ su31o4gj83:不会挤啦, 你的程式码还蛮整齐的, 风格跟我蛮类似的 08/12 22:01
20F：→ su31o4gj83:我的程式码会比你的再挤一点, 像是一行码我都不加{} 08/12 22:03
21F：→ su31o4gj83:我的好读是指结构清楚, 搭配一点注解就很好读的程式 08/12 22:05
22F：→ su31o4gj83:你的写作习惯我觉得没什麽问题, 不用担心 :) 08/12 22:07