發表新討論
#40936: 解答 C++


hs210023@students.hshs.chc.edu ... (天底下最帥的那個男人)

a121. 質數又來囉 | From: [111.253.30.225] | 發表日期: 2024-06-19 13:59
要解決這個問題，我們需要一個方法來判斷一個數字是否為質數，然後在給定範圍內統計質數的數量。由於範圍不大（b-a <= 1000），可以用簡單的篩選法來實現。

 

以下是用 C++ 寫的一個解決方案：
 
#include <iostream>
#include <cmath>
using namespace std;

// 判斷一個數字是否為質數
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int main() {
    int a, b;
    while (cin >> a >> b) {
        int primeCount = 0;
        for (int i = a; i <= b; ++i) {
            if (isPrime(i)) {
                ++primeCount;
            }
        }
        cout << primeCount << endl;
    }
    return 0;
}

 

程式說明

 

  1. **函數 isPrime(int n)**：
    • 判斷一個數字 n 是否為質數。
    • 如果 n 小於等於 1，則不是質數。
    • 如果 n 小於等於 3，則是質數。
    • 如果 n 能被 2 或 3 整除，則不是質數。
    • 使用 for 迴圈從 5 開始檢查，步長為 6，檢查 n 是否能被任一小於等於 sqrt(n) 的數字整除。
  2. **主函數 main()**：
    • 不斷讀取輸入的兩個正整數 a 和 b。
    • 初始化質數計數器 primeCount 為 0。
    • 使用 for 迴圈從 a 遍歷到 b，對每個數字調用 isPrime 函數進行檢查，如果是質數則計數器加 1。
    • 輸出計數器的值。

 

範例輸入與輸出

 

根據範例輸入：
 
3 7
6 6
30 50

 

輸出應為：

 

 
3
0
5

 

這個程式會根據輸入的範圍，計算並輸出範圍內的質數數量。每組輸入獨立處理，直到輸入結束。
ZeroJudge Forum