一.首先解決n的質數的問題

（1）枚舉法

???? ??考慮質數的定義：在大于 1的自然數中，除了 1 和它本身以外不再有其他因數的自然數。因此對于每個數 x，我們可以從小到大枚舉 [2,x?1] 中的每個數 y，判斷 y是否為 x的因數。但這樣判斷一個數是否為質數的時間復雜度最差情況下會到 O(n)，無法通過所有測試數據。
???? ??就不寫代碼了

???? ??枚舉沒有考慮到數與數的關聯性，因此難以再繼續優化時間復雜度。接下來我們介紹一個常見的算法，該算法由希臘數學家厄拉多塞（Eratosthenes\rm EratosthenesEratosthenes）提出，稱為厄拉多塞篩法，簡稱埃氏篩。

（2）埃氏篩

以下是埃氏篩法的步驟：

1.創建一個大小為 n+1 的布爾數組 is_prime，并將所有元素初始化為 True。數組的索引代表數字，True 表示該數字是質數，False 表示該數字是合數。
2.將 is_prime[0] 和 is_prime[1] 設置為 False，因為 0 和 1 不是質數。
3.從索引 2 開始，遍歷數組。如果當前索引 i 是質數（即 is_prime[i] 為 True），則將所有 i 的倍數（從 i^2開始，小于等于 n）標記為 False，表示這些數不是質數。
4.遍歷完成后，所有 is_prime 數組中值為 True 的索引即為小于等于 n 的質數。

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>// 函數聲明
void sieve_of_eratosthenes(int n);int main() {int n = 30;printf("小于等于 %d 的質數:\n", n);sieve_of_eratosthenes(n);return 0;
}// 實現埃拉托色尼篩法
void sieve_of_eratosthenes(int n) {// 動態分配一個布爾數組，并初始化為 truebool *is_prime = (bool*) malloc((n + 1) * sizeof(bool));for (int i = 0; i <= n; i++) {is_prime[i] = true;}is_prime[0] = is_prime[1] = false; // 0 和 1 不是質數for (int p = 2; p * p <= n; p++) {// 如果 is_prime[p] 沒有被標記為 false，則 p 是一個質數if (is_prime[p] == true) {// 將所有 p 的倍數標記為 falsefor (int i = p * p; i <= n; i += p) {is_prime[i] = false;}}}// 打印所有的質數for (int p = 2; p <= n; p++) {if (is_prime[p]) {printf("%d ", p);}}printf("\n");// 釋放動態分配的內存free(is_prime);
}

二.解決n的質數約數問題

要找出一個整數 n 的所有質數約數，我們可以通過以下步驟實現：

1.使用埃拉托色尼篩法生成小于等于 n 的所有質數。
2.遍歷這些質數，檢查它們是否是 n 的約數。
3.輸出所有質數約數。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 函數聲明
void sieve_of_eratosthenes(int n, bool* is_prime);
void print_prime_factors(int n, bool* is_prime);int main() {int n;printf("請輸入一個整數: ");scanf("%d", &n);// 動態分配一個布爾數組，用于存儲質數信息bool *is_prime = (bool*) malloc((n + 1) * sizeof(bool));sieve_of_eratosthenes(n, is_prime);printf("%d 的質數約數是: ", n);print_prime_factors(n, is_prime);// 釋放動態分配的內存free(is_prime);return 0;
}// 實現埃拉托色尼篩法
void sieve_of_eratosthenes(int n, bool* is_prime) {for (int i = 0; i <= n; i++) {is_prime[i] = true;}is_prime[0] = is_prime[1] = false; // 0 和 1 不是質數for (int p = 2; p * p <= n; p++) {if (is_prime[p] == true) {for (int i = p * p; i <= n; i += p) {is_prime[i] = false;}}}
}// 打印 n 的質數約數
void print_prime_factors(int n, bool* is_prime) {for (int i = 2; i <= n; i++) {if (is_prime[i] && n % i == 0) {printf("%d ", i);}}printf("\n");
}

代碼解析：
1.使用 sieve_of_eratosthenes 函數生成小于等于 n 的所有質數，并將結果存儲在布爾數組 is_prime 中。
2.使用 print_prime_factors 函數遍歷所有小于等于 n 的數，如果該數是質數且是 n 的約數，則將其打印出來。
3.在 main 函數中，輸入一個整數 n，并調用上述兩個函數來生成質數并打印質數約數。