C語言程式判斷一個數是否為質數

質數是指只能被1和自身整除的數。一個數的因數是可以整除它的數。

前十個質數是：2, 3, 5, 7, 11, 13, 17, 23, 29, 31。

非質數稱為合數。合數是可以被多個數整除的數。

除了質數和合數之外，還有1，它既不是質數也不是合數，因為它只能被自身整除。

如何檢查一個數是質數還是合數？要檢查一個數是否為質數，需要檢查以下兩個條件：

1) 它必須是一個大於1的整數。

2) 它只能有兩個因數，即1和自身。

如果滿足這兩個條件，則該數為質數。

在我們的程式中，我們將透過將該數除以小於該數的每個數來進行檢查。如果任何小於給定數的數都能整除它，則它不是質數。否則，它是一個質數。

示例

讓我們以兩個數為例，並使用此方法檢查它們是否為質數。

Input − Number1 − 42
Output − 42 is not a prime number

邏輯

我們將42除以每個大於1且小於42的數。所以：

42/2 = 21，即42可以被2整除，這意味著42不是質數，因為它可以被其他數整除。

Input − Number2 − 7
Output − 7 is a prime number

邏輯解釋

我們將7除以每個大於1且小於7的數。所以：

7不能被2整除，因此程式碼將檢查下一個數，即3。

7不能被3整除，因此程式碼將檢查下一個數，即4。

7不能被4整除，因此程式碼將檢查下一個數，即5。

7不能被5整除，因此程式碼將檢查下一個數，即6。

7不能被6整除，這意味著7只能被1和7整除，這意味著7是一個質數。

看看上面的邏輯，如果數字超過1000甚至100000，那麼程式將需要進行那麼多次迴圈迭代，這種方法將需要大量的計算時間。因此，為了減少迭代次數，必須有更好的方法。

一個最佳化的解決方案是隻執行for迴圈到一半。這意味著如果數字是77，迴圈將只執行到38。這將減少所需的迭代次數，因此我們將使用此演算法來建立我們的程式。

示例

#include <stdio.h>
int main() {
   int num = 33, flag = 0;
   for(int i=2 ; i < num/2 ; i++) {
      if(num%i == 0) {
         printf("%d is not a prime number", num);
         flag = 1;
         break;
      }
   }
   if(flag == 0) {
      printf("%d is a prime number", num);
   }
}

輸出

33 is a prime number

sudhir sharma

更新於：2023年11月7日

4萬+ 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習