a121 - 質數又來囉
題目描述
題目要求計算給定區間 [a, b] (包含 a 和 b) 內質數的個數。輸入兩個正整數 a 和 b，輸出區間內的質數數量。
解題思路
此題採用暴力法求解。對於區間 [a, b] 中的每個數字 j，從 2 到 sqrt(j) 進行迴圈，檢查 j 是否能被任何數字整除。如果 j 不能被任何數字整除，則 j 是質數，計數器 i 增加。 特別注意，如果 a 或 b 等於 1，則需要將計數器 i 減 1，因為 1 不是質數。
複雜度分析
- 時間複雜度: O(n * sqrt(n))，其中 n 是 b - a + 1。因為對於區間內的每個數字，我們都需要進行到 sqrt(j) 的迴圈檢查。
- 空間複雜度: O(1)，因為我們只使用了常數個額外的變數。
程式碼
#include <iostream>
#include <math.h>
using namespace std;
int main(){
long long int a=0,b=0;
int i=0;
bool c=true;
while(cin >> a >> b){
if(b>=a){
for(long long int j=a;j<=b;j++){
for(long long int k=2;k<=sqrt(j);k++){
if(j%k==0){
c=false;
break;
}
}
if(c==true){
i++;
}
c=true;
}
if(a==1||b==1){
i--;
}
cout << i << endl;
i=0;
}
else{
cout << 0 << endl;
}
}
}