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

[SiriusJinn (假斯汀)]

下面是我的程式碼，在線上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
推 VictorTom:1個可以加速的地方是, 迴圈跑到根號x就夠了:)
→ iamivers0n:篩法
→ SiriusJinn:那可以直接把for裡的x改成pow(x,0.5)嗎？
→ SiriusJinn:啊啊~我發現有個地方打錯了 = =
→ pico2k:m=0可以拿到for迴圈之外
→ pico2k:開根號求出來的值是double...
→ SiriusJinn:嗯呀~這樣似乎有問題耶...
→ SiriusJinn:我用強制轉換看看
推 ledia:迴圈每次都要算一次 pow 會不會太慢了 可以先算好 又不會變
→ ledia:pow 比 sqrt 慢
→ SiriusJinn:好的，我用代數取代試試
推 legnaleurc:i*i < x
→ secondsee:x=sqrt(x);
推 yyuto:sqrt複雜度很高 建議使用L大提的i*i<x
→ SiriusJinn:若令一個y=(int)(pow(x,0.5))這樣y是整數嗎？
→ SiriusJinn:用了i*i<x 結果"4"判斷為質數耶= =
推 Fenikso:i*i <= x
推 VictorTom:雖然用i*i<=x比較快, 可是算根號也只需要做一次啊XD
→ VictorTom:至於pow/sqrt算出來是double的問題, 直接+0.5取整就好:)
推 VictorTom:個人建議, 不需要才這種狀況就寫下goto....
→ SiriusJinn:我想說能不能加快個執行速度耶...
推 liangjr:篩法會快很多
→ liangjr:http://zh.wikipedia.org/wiki/埃拉托斯特尼筛法
推 ledia:篩法會不會比較快也要看查幾次~
→ ledia:不過篩法的好處是篩一次出來就可以 binary search (or hash)
→ SiriusJinn:我解決了 = = 改用y=(int)(sqrt(x))後不會逾時就過了
→ SiriusJinn:然後把start改成break
→ SiriusJinn:我補一下我的寫法好了
※ 編輯: SiriusJinn      來自: 140.120.90.174       (07/23 18:00)
→ SiriusJinn:為了加快速度，for迴圈裡的東西果然是越少越好
推 liangjr:篩法最強的是建一次表之後就可以查表沒錯
→ liangjr:但就算只用一次 篩法還是會比現在的方法快
→ liangjr:就算是篩法最基本的 篩掉2的倍數不檢查 速度就會快很多了
→ liangjr:迴圈可以改成 i=3; i<=y; i+=2, x=2的情況另外判斷