PTT數位生活區 / C_and_CPP (C/C++)

[問題] 判斷是否質數演算法會逾時

看板C_and_CPP (C/C++)作者 (假斯汀)時間16年前 (2009/07/22 18:05), 編輯推噓10(10推 0噓 23→)
留言33則, 10人參與, 最新討論串1/1
下面是我的程式碼，在線上judge時執行時間太久了 有什麼地方可以修改或有更好的演算法可以用嗎？ 希望大家給個建議！謝謝~ 修正過後有點小問題，持續逾時中 = =" ===================================================== #include <stdio.h> #include <math.h> int main(void) { int x,y,i,m=0; while(scanf("%d",&x)!=EOF) { y=(int)(sqrt(x)); for(i=2;i<=y;i++) { if(x%i==0) { m=1; printf("非質數\n"); break; } } if(m==0) printf("質數\n"); m=0; } return 0; } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.120.90.174
推
07/22 18:09, , 1F
1個可以加速的地方是, 迴圈跑到根號x就夠了:)
07/22 18:09, 1F
→
07/22 18:23, , 2F
篩法
07/22 18:23, 2F
→
07/22 18:23, , 3F
那可以直接把for裡的x改成pow(x,0.5)嗎？
07/22 18:23, 3F
→
07/22 18:26, , 4F
啊啊~我發現有個地方打錯了 = =
07/22 18:26, 4F
→
07/22 18:30, , 5F
m=0可以拿到for迴圈之外
07/22 18:30, 5F
→
07/22 18:31, , 6F
開根號求出來的值是double...
07/22 18:31, 6F
→
07/22 18:35, , 7F
嗯呀~這樣似乎有問題耶...
07/22 18:35, 7F
→
07/22 18:40, , 8F
我用強制轉換看看
07/22 18:40, 8F
推
07/22 18:44, , 9F
迴圈每次都要算一次 pow 會不會太慢了 可以先算好 又不會變
07/22 18:44, 9F
→
07/22 18:46, , 10F
pow 比 sqrt 慢
07/22 18:46, 10F
→
07/22 18:47, , 11F
好的，我用代數取代試試
07/22 18:47, 11F
推
07/22 18:57, , 12F
i*i < x
07/22 18:57, 12F
→
07/22 19:01, , 13F
x=sqrt(x);
07/22 19:01, 13F
推
07/22 19:12, , 14F
sqrt複雜度很高 建議使用L大提的i*i<x
07/22 19:12, 14F
→
07/22 19:12, , 15F
若令一個y=(int)(pow(x,0.5))這樣y是整數嗎？
07/22 19:12, 15F
→
07/22 19:16, , 16F
用了i*i<x 結果"4"判斷為質數耶= =
07/22 19:16, 16F
推
07/22 19:24, , 17F
i*i <= x
07/22 19:24, 17F
推
07/22 19:45, , 18F
雖然用i*i<=x比較快, 可是算根號也只需要做一次啊XD
07/22 19:45, 18F
→
07/22 19:46, , 19F
至於pow/sqrt算出來是double的問題, 直接+0.5取整就好:)
07/22 19:46, 19F
推
07/22 20:50, , 20F
個人建議, 不需要才這種狀況就寫下goto....
07/22 20:50, 20F
→
07/22 21:39, , 21F
我想說能不能加快個執行速度耶...
07/22 21:39, 21F
推
07/23 17:31, , 22F
篩法會快很多
07/23 17:31, 22F
→
07/23 17:32, , 23F
http://zh.wikipedia.org/wiki/埃拉托斯特尼筛法
07/23 17:32, 23F
推
07/23 17:49, , 24F
篩法會不會比較快也要看查幾次~
07/23 17:49, 24F
→
07/23 17:49, , 25F
不過篩法的好處是篩一次出來就可以 binary search (or hash)
07/23 17:49, 25F
→
07/23 17:58, , 26F
我解決了 = = 改用y=(int)(sqrt(x))後不會逾時就過了
07/23 17:58, 26F
→
07/23 17:59, , 27F
然後把start改成break
07/23 17:59, 27F
→
07/23 17:59, , 28F
我補一下我的寫法好了
07/23 17:59, 28F
※ 編輯: SiriusJinn 來自: 140.120.90.174 (07/23 18:00)
→
07/23 18:01, , 29F
為了加快速度，for迴圈裡的東西果然是越少越好
07/23 18:01, 29F
推
07/23 18:16, , 30F
篩法最強的是建一次表之後就可以查表沒錯
07/23 18:16, 30F
→
07/23 18:17, , 31F
但就算只用一次 篩法還是會比現在的方法快
07/23 18:17, 31F
→
07/23 18:18, , 32F
就算是篩法最基本的 篩掉2的倍數不檢查 速度就會快很多了
07/23 18:18, 32F
→
07/23 18:19, , 33F
迴圈可以改成 i=3; i<=y; i+=2, x=2的情況另外判斷
07/23 18:19, 33F
‣ 更多 SiriusJinn 的文章
文章代碼(AID): #1APkI3X2 (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 SiriusJinn 的文章
文章代碼(AID): #1APkI3X2 (C_and_CPP)