Re: [問題] 小弟寫了一個程式 就差了一點

看板C_and_CPP (C/C++)作者 ( )時間16年前 (2009/08/12 18:39), 編輯推噓3(3019)
留言22則, 3人參與, 最新討論串2/3 (看更多)
小弟我也是個剛學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

08/12 18:41, , 1F
我自覺這寫法結果雖然是正確的 但效率非常低 0rz
08/12 18:41, 1F

08/12 18:46, , 2F
純找小於N的質數的話, 有個常見的作法是 篩法 :)
08/12 18:46, 2F

08/12 18:55, , 3F
如果你要找質因數的話i不用跑完, 不過所有因數的話....
08/12 18:55, 3F

08/12 18:58, , 4F
呵~我看到你的質因數測試器了
08/12 18:58, 4F

08/12 19:01, , 5F
其實所有的因數的話也不用跑完, 一半就可以了
08/12 19:01, 5F

08/12 19:10, , 6F
其實那是質數測試器, 只是因為餵給它的是因數....XD
08/12 19:10, 6F

08/12 19:11, , 7F
yes, 我本來是寫n/2, 不過後來想到n本身也是因數,但是去
08/12 19:11, 7F

08/12 19:11, , 8F
話說不用跑一半啦, 跑根號p就夠了:)
08/12 19:11, 8F

08/12 19:12, , 9F
掉 1/2 factor 又增加太多計算了
08/12 19:12, 9F

08/12 19:13, , 10F
是沒錯 不過我不知道有沒有預設的sqrt() 沒有的話要額外
08/12 19:13, 10F

08/12 19:14, , 11F
math.h有sqrt吧?? 還是得用pow(n,0.5)?? 有點忘了....
08/12 19:14, 11F

08/12 19:15, , 12F
話說, 其實還是重複算很多, 這時候篩下去比較爽啦XD
08/12 19:15, 12F

08/12 19:34, , 13F
有 thanks
08/12 19:34, 13F

08/12 20:37, , 14F
另外, 可以考慮移除primetest, 直接放到main的for loop
08/12 20:37, 14F

08/12 20:41, , 15F
跑一半我是想說/2比sqrt省, 不過應該還是用sqrt比較好
08/12 20:41, 15F

08/12 20:43, , 16F
畢竟數字大一點, 用sqrt可少跑很多步
08/12 20:43, 16F

08/12 20:48, , 17F
我是覺得有時候程式好讀比效能重要XD
08/12 20:48, 17F

08/12 21:39, , 18F
哈 我寫的太擠了
08/12 21:39, 18F

08/12 22:01, , 19F
不會擠啦, 你的程式碼還蠻整齊的, 風格跟我蠻類似的
08/12 22:01, 19F

08/12 22:03, , 20F
我的程式碼會比你的再擠一點, 像是一行碼我都不加{}
08/12 22:03, 20F

08/12 22:05, , 21F
我的好讀是指結構清楚, 搭配一點註解就很好讀的程式
08/12 22:05, 21F

08/12 22:07, , 22F
你的寫作習慣我覺得沒什麼問題, 不用擔心 :)
08/12 22:07, 22F
文章代碼(AID): #1AWflXtN (C_and_CPP)
文章代碼(AID): #1AWflXtN (C_and_CPP)