昨天天烆問我ZeroJudge上的質數問題要怎麼解,說真的,我不會XD
兩個人只好直接拜見Google大神,也找到了一個自己也不知道為什麼但卻通過的程式碼(汗
於是今天就去問數學老師關於質數檢查的問題,他表示這基本上還是要一個一個去檢查,但有個比較快的方法,就是只檢查到原數開根號的數字
接下來就是回家實作的時間~~
大概花了兩小時就完成了,執行檔可以在這裡下載
但要記得裝VC++2010函式庫:http://atifans.net/download/code/prime_number_checker.rar
//存取所需函式 #include <stdio.h> #include <math.h> //主程式 int main(void){ //定義變數 int test,input,checked; float input_sqrt; printf("這支程式用來檢測一個數字是否為質數,可輸入-1來退出程式\n\n"); while(1){ printf("要檢查的數字:"); scanf_s("%d", &input); if(input == EOF) //檢查輸入數字的有效性 break; if(input == 2){ printf("結果:質數\n\n"); }else if(input == 1){ printf("結果:這是1\n\n"); }else if((input % 2) == 0){ printf("結果:非質數,最小因數為2\n\n"); }else{ checked = 0; input_sqrt = sqrt((float)input); for(test = 3; test <= input_sqrt; test += 2){ if((input % test) == 0){ printf("結果:非質數,最小因數為%d\n\n", test); checked = 1; break; } } if(checked != 1) printf("結果:質數\n\n"); } } return 0; }
還有一個更快的方法就是用質數表下去除了
@kgame
在(2^31)-1的情況下當然是可行啦... {= =|||}
想想看大於(2^31)-1 ,甚至大於2^64的整數問題如何解
@kgame
據說(?)是用array {|||}
最近都習慣用篩法來做
超過64位元整數範圍的數值 只要建立好大數的系統應該也能使用相同的方法吧
不知道是否有效率更高的作法就是了A_A
@NiwaSho Lin
聽起來好像很複雜 {||||}
這個程式有 bug ,它會把 1 當成質數。
感謝告知,當時沒注意到XD