ATI的軟體&網管技術誌

奇怪的網站

| 8 則留言

[C語言] 質數檢查器

昨天天烆問我ZeroJudge上的質數問題要怎麼解，說真的，我不會XD

兩個人只好直接拜見Google大神，也找到了一個自己也不知道為什麼但卻通過的程式碼(汗

於是今天就去問數學老師關於質數檢查的問題，他表示這基本上還是要一個一個去檢查，但有個比較快的方法，就是只檢查到原數開根號的數字

接下來就是回家實作的時間~~

大概花了兩小時就完成了，執行檔可以在這裡下載
但要記得裝VC++2010函式庫：https://atifans.net/download/code/prime_number_checker.rar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//存取所需函式
#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. 還有一個更快的方法就是用質數表下去除了

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

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

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

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

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

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