# 質數題目

:::spoiler 完整程式

#include <stdio.h>

int main(){
    int input = 0;
    int detection = 0; // 0 = false, 1 = true
    printf("enter a number: ");
    scanf("%d", &input);

    for (int i = input - 1; i > 1; i --){
        if(input % i == 0){
            detection = 1;
            break;
        }
    }

    if(detection == 1){
        printf("%d is not a prime number\n", input);
    }
    else{
        printf("%d is a prime number\n", input);
    }

    return 0;
}

:::

## 概念
用for迴圈，i一開始等於 「輸入的數字-1」，重複條件是 「大於1」，持續變小，迴圈中如果input「模除」{i|持續變小}等於0，代表這個數可以被整除，也就代表這個數不是質數

>模除：模數除法，簡單來說就是取餘數
> >a % b = c
> >就是 a ÷ b = {x|商} ... c

我用一個整數 {detection|偵測的英文} 當作儲存判斷的地方，如果detection等於1就代表他不是質數

## ChatGPT
在C語言中判斷一個數字是否為質數，除了您提到的模除方法外，還有一些其他的方法可以使用。這裡介紹幾種常見的方法：

1. **平方根方法**：這是對模除方法的一種優化。由於一個非質數必然有一個因數不大於其平方根，所以只需要檢查到該數字的平方根即可。這大大減少了迴圈的次數。

   #include <math.h>
   #include <stdbool.h>

   bool isPrime(int number) {
       if (number <= 1) return false;
       for (int i = 2; i <= sqrt(number); i++) {
           if (number % i == 0) return false;
       }
       return true;
   }

2. **埃拉托斯特尼篩法（Sieve of Eratosthenes）**：這是一種找出一定範圍內所有質數的高效方法。它的原理是從2開始，先找到第一個質數2，然後去除2的所有倍數，再找到下一個質數並去除其倍數，依此類推。

   #include <stdbool.h>
   #include <string.h>

   void sieveOfEratosthenes(int n, bool prime[]) {
       memset(prime, true, sizeof(bool) * (n+1));
       prime[0] = prime[1] = false;
       for (int p = 2; p*p <= n; p++) {
           if (prime[p] == true) {
               for (int i = p*p; i <= n; i += p)
                   prime[i] = false;
           }
       }
   }

使用這個方法，可以高效地找出一定範圍內的所有質數，然後可以直接檢查某個數字是否為質數。

3. **6k±1規則**：除了2和3之外的所有質數，都可以表示成6k±1的形式（k是一個自然數）。基於這個規則，我們可以只檢查形式為6k±1的數字，這也是一種優化。

   bool isPrime(int number) {
       if (number <= 1) return false;
       if (number <= 3) return true;

       if (number % 2 == 0 || number % 3 == 0) return false;

       for (int i = 5; i * i <= number; i += 6) {
           if (number % i == 0 || number % (i + 2) == 0) return false;
       }
       return true;
   }

這些方法各有優缺點，可以根據具體的應用場景選擇合適的方法。平方根方法適合單次判斷質數，埃拉托斯特尼篩法適合大規模篩選質數，6k±1方法則在某些情況下能提供更好的性能。