[C語言] 質數檢查器

昨天天烆問我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;
}

留言

  1. 還有一個更快的方法就是用質數表下去除了

    • @kgame
      在(2^31)-1的情況下當然是可行啦... {= =|||}

  2. 想想看大於(2^31)-1 ,甚至大於2^64的整數問題如何解

  3. 最近都習慣用篩法來做

    超過64位元整數範圍的數值 只要建立好大數的系統應該也能使用相同的方法吧

    不知道是否有效率更高的作法就是了A_A

  4. 這個程式有 bug ,它會把 1 當成質數。

    • 感謝告知,當時沒注意到XD

粗體斜體刪除線連結引用圖片程式碼

注意:您的電子信箱將不會被公開,且網站連結不會被搜尋引擎採計

{124} {123} {122} {121} {120} {119} {118} {117} {116} {115} {114} {113} {112} {111} {100} {025} {024} {023} {022} {021} {020} {019} {018} {017} {016} {015} {014} {013} {012} {011} {010} {009} {008} {007} {006} {005} {004} {003} {002} {001}