###### tags: `APCS`
# **課堂練習－找質數**
### **題目解析**
找出從 1 到 N 的所有質數。質數是指除了 1 和其本身以外，沒有其他因數的自然數。這裡給出了兩個版本的程式碼來解決這個問題。
### **解題方向**
* 版本一：使用簡單的雙重迴圈來檢查每個數是否為質數。這種方法的時間複雜度較高，因為對每個數進行了完全的因數檢查。
* 版本二：使用改進的籃子法（Sieve of Eratosthenes），僅檢查可能的質數因數到數字的平方根，提高效率。
* 版本三：使用Eratosthenes sieve method來撰寫，以一個陣列來記錄每個數是否為質數。
### **程式解析**
* 版本一
* 讀取輸入的整數 N。
* 使用雙重迴圈，外層迴圈遍歷從 1 到 N 的所有數字。
* 對於每個數字 i，內層迴圈檢查從 2 到 i 的所有數字，判斷是否為質數。
* 如果 i 是質數，將其加入質數列表。
* 輸出質數列表及程式執行時間。
* 版本二
* 讀取輸入的整數 N。
* 使用雙重迴圈，但內層迴圈僅遍歷從 2 到數字的平方根，提高檢查效率。
* 如果數字 i 是質數，將其加入質數列表。
* 輸出質數列表及程式執行時間。
* 版本三
* 陣列元素a[i]表示i仍然可能是質數。
* 若a[i]=0表示i並非質數。
* 若i確定是質數時，將全部a[k]清除為0，其中k為i的整數倍。
### **完整程式碼**
版本一

import time

# start
N = int(input())

start_time = time.time()

prime = []

for i in range(1, N+1):
    isPrime = True
    for j in range(2, i+1):
        if i % j == 0 and j != i:
            isPrime = False

        elif j == i and isPrime == True:
            prime.append(i)

print(prime)
end_time = time.time()

print("execution time:", (end_time - start_time), "s")

版本二

import time
import math

# start
N = int(input())

start_time = time.time()

prime = []

for i in range(2, N+1):
    isPrime = True

    end = int(math.sqrt(i))

    for j in range(2, end+1):
        if i % j == 0:
            isPrime = False
            break  # 提早結束檢查

    if isPrime:
        prime.append(i)

end_time = time.time()

print(prime)
print("execution time:", (end_time - start_time), "s")

版本三

n = int(input("Enter a number: "))
a = [1] * (n + 1)  # 初始化列表，大小為 n+1（包括 0）

for i in range(2, n + 1):
    if a[i]:  # 如果 a[i] 為 1，則表示 i 是質數
        print(i, end=' ')  # 輸出質數
        k = i * i  # 從 i 的平方開始標記
        while k <= n:
            a[k] = 0  # 將 i 的倍數標記為非質數
            k += i
print()

### 詳細解析
版本一
* N = int(input())：讀取輸入的整數 N。
* start_time = time.time()：記錄程式開始執行時間。
* prime = []：初始化存儲質數的列表。
* for i in range(1, N+1):：遍歷 1 到 N 的所有數字。
* isPrime = True：假設數字 i 是質數。
* for j in range(2, i+1):：檢查從 2 到 i 的所有數字。
* if i % j == 0 and j != i:：如果 i 可以被 j 整除且 j 不是 i 本身，則 i 不是質數。
* elif j == i and isPrime == True:：如果內層迴圈到達 i 且 isPrime 仍為 True，則 i 是質數，將其加入列表。
* print(prime)：輸出質數列表。
* end_time = time.time()：記錄程式結束執行時間。
* print("execution time:", (end_time - start_time), "s")：輸出程式執行時間。

版本二
* N = int(input())：讀取輸入的整數 N。
* start_time = time.time()：記錄程式開始執行時間。
* prime = []：初始化存儲質數的列表。
* for i in range(2, N+1):：遍歷 2 到 N 的所有數字。
* isPrime = True：假設數字 i 是質數。
* end = int(math.sqrt(i))：計算數字 i 的平方根。
* for j in range(2, end+1):：檢查從 2 到 i 平方根的所有數字。
* if i % j == 0:：如果 i 可以被 j 整除，則 i 不是質數，設置 isPrime = False 並提早結束檢查。
* if isPrime:：如果 isPrime 仍為 True，則 i 是質數，將其加入列表。
* end_time = time.time()：記錄程式結束執行時間。
* print(prime)：輸出質數列表。
* print("execution time:", (end_time - start_time), "s")：輸出程式執行時間。

版本三
* n = int(input("Enter a number: "))：讀取輸入的整數 𝑛。
* a = [1] * (n + 1)：初始化列表 a，大小為 𝑛 + 1 ，所有元素設為 1。
* 這裡 a[i] 表示數字 𝑖 是否為質數，初始假設所有數字都是質數。
* for i in range(2, n + 1)：從 2 開始遍歷到 𝑛 。
* if a[i]：如果 a[i] 為 1，表示 𝑖 是質數。
* print(i, end=' ')：輸出質數 𝑖 。
* k = i * i：從 𝑖 的平方開始標記 𝑖 的倍數。
* while k <= n：迴圈從 𝑘（即 𝑖 的平方）開始標記到 𝑛。
* a[k] = 0：將 𝑖 的倍數標記為非質數。
* k += i：移動到下一個倍數。
* 最後，所有 a[i] 仍為 1 的位置即為質數。