歡迎加入我的 Discord 群組與我討論程式相關的問題!

Posted on 

 by 

 in 

Zerojudge a121. 質數又來囉

評分:1 分,滿分為 5。

題目連結

題意

給兩個整數 a, b。問 a, b 之間有幾個質數 (包含 a, b)

解題方法

先不要看到數字範圍是 10^9 次方就覺得這題做不了! 題目有保證 b – a <= 1000,
所以我們只要檢查 1000 個數字有幾個質數就可以了。

檢查的話,還記得質數的定義是除了自己跟 1 沒有其他因數嗎,
我們可以從 2 跑到 x 看看有沒有人可以被 x 整除,有的話就不是質數。
但是這樣的複雜度會變成 O(10^9 * 1000) 顯然太慢了。

觀察因數我們可以發現,因數是一對一對的,而一對當中一定有一個 <= 根號 x ,
一個 >= 根號 x,要不然如果兩個都 > 根號 x 的話乘起來就超過 x 了。

因此,我們檢查只需要跑到 sqrt(x) 就可以了!由於這題題目不清楚,並沒有說
最多會給多少個 a, b 所以每次一找到因數就 break 才會過喔 

一個a, b的複雜度: O(10^4.5 * 1^3) = O(10^7.5)

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int a, b;
    while(cin >> a >> b){
	int ans = 0;
	for(int x = a;x <= b;x++){
	    if(x == 1) continue;
	    int ok = 1;
	    for(int i = 2;i*i <= x;i++){ // <= sqrt(x)
		if(x % i == 0) {
		    ok = 0;
		    break; // 一找到就馬上break才會過
		}
	    }
	    ans += ok;
        }
	cout << ans << '\n';
    }
}

發表迴響

Blog at WordPress.com.

%d 位部落客按了讚: