[問題] 有更快的求質數方法嗎？

[Savate (薩瓦特)]

遇到的問題：

我寫了一個程式，輸入一個數，計算此數是否為質數。
有故意輸入2147483647但是跑很久。
但不知道還有更快的方式嗎？
程式中設一個陣列存放質數感覺會很吃記憶體。

另外，變換視窗之後，除數會偷跑變成很大的數？
怎麼會這樣子呢？


希望得到的正確結果：
希望能知道有更快的方式或點子或想法
目前有在修資料結構


程式跑出來的錯誤結果：無


開發平台： dev C  Windows


有問題的code：
http://nopaste.info/c1eb7bcf54.html

補充說明：
第12行昨天寫 while(i*i<=g)
然後輸入2147483647結果跑了快半小時
被除數都已經八位數了
我才發覺好像怪怪的  = =

--

http://tinyurl.com/yclru5x
爸爸和女兒在喜宴中大打出手

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 163.25.115.99
推 dendrobium:什麼叫做變換視窗？
推 littleshan:這個程式跑很慢的原因是你不斷呼叫 printf
→ littleshan:和整數運算比起來，I/O 可是很緩慢的操作
推 ledia:因為 i*i 溢位了, 試試 long long int 或是 i <= g/i
→ ledia:或是直接把 x=(int)sqrt(g); 求出來, i<=x 就好
→ MOONRAKER:如果你的程式只做一件事情，計較放質數的記憶體空間還
→ MOONRAKER:滿無聊的。
→ Savate:回樓上  還有一個問題是我不知道我該設多少個
推 andyjy12:我還以為有人要回說:"只有量子電腦解質數才能快" XD
推 VictorTom:建一個2G的質數test table, 應該很快....XD
→ VictorTom:寫省一點的話至少把2的3的5的先去掉, 可以少幾倍XDDD
→ joefaq:你可以參考Miller-Rabin
→ DJWS:要保證結果正確的話，可嘗試AKS演算法。頗複雜就是了。
→ DJWS:Miller-Rabin的結果可能會出錯。它比較容易理解和實作。
推 Fenikso:Miller-Rabin對2^32以下的數也可以保證答對
→ Fenikso:數字要挑過就是
推 costbook:量子電腦啊～～～好久以前的文章了
推 Fenikso:而且只要測三個數字
→ bobhsiao:這種題目到最後就變成考數學啦
推 tw00088437:推量子電腦
推 bugmens:作業等級執行時間和記憶體空間就別太計較了
→ bugmens:寫得出來觀念正確比較重要
→ MOONRAKER:不知道你該設多少個？那就隨便設一個啊
→ MOONRAKER:你做過實驗吧？計算機的實驗還不會受傷哩！
→ MOONRAKER:不滿意，就改大點再實驗，頂多當掉而已，有什麼好怕的
→ poga:去抓個質數表下來查表就很好用了