題目連結 http://zerojudge.tw/ShowProblem?problemid=a121。
維基百科上質數的定義為:
「指在大於1的自然數中,除了1和該數自身外,無法被其他自然數整除的數(也可定義為只有1與該數本身兩個因數的數)」
一個著名且有效率的方法Sieve of Eratosthenes(底下圖片取自https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
一個著名且有效率的方法Sieve of Eratosthenes(底下圖片取自https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
Sieve of Eratosthenes演算法(底下文字取自https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes):
筆者先用Sieve of Eratosthenes演算法求出100000000以下的所有質數的對照表,接著再用迴圈檢查 [a,b] 範圍內有多少個質數。
程式碼:
#include <cmath>
#include <vector>
#include <iostream>
using namespace std;
#define NUM 100000001
int main(int argc, char** argv) {
vector<bool> isP;
long cnt;
long a, b;
for(int i = 0; i < NUM; i++)
isP.push_back(true);
isP[0] = false;
isP[1] = false;
for(long i = 2; i <= 10000; i++)
{
if(isP[i])
{
for(long j = i * i; j < NUM; j += i)
isP[j] = false;
}
}
while(cin >> a >> b)
{
cnt = 0;
for(long i = a; i <= b; i++)
{
if(isP[i]) cnt++;
}
cout << cnt << endl;
}
return 0;
}
沒有留言:
張貼留言