大神的世界

建立質數表

迴圈

輸入上下限

找尋第一個>=下限的質數且不超過陣列元素

找尋第一個>上限的質數且不超過陣列元素

輸出個數

PS:這題因為上下限差不到1000

     所以不建表反而更快

#include <iostream>
#include <cstring>

#define N 100000000

using namespace std;

bool bPrime[N];
int prime[5761456];
int primeNum = 0;

void setPrimeTable()
{
    primeNum = 0;

    memset(bPrime, true, N);
    memset(prime, 0, sizeof(prime));

    bPrime[0] = bPrime[1] = false;

    for(int i = 2; i<N; i++)
        if(bPrime[i])
        {
            prime[primeNum++] = i;
            for(int j = i; j<N; j+=i)
                bPrime[j] = false;
        }
}

int main()
{
    setPrimeTable();

    int a, b;
    int i;
    int ans;

    while(cin >> a >> b)
    {
        for(i = 0; prime[i] < a && i<primeNum; i++);

        ans = 0;
        for(; prime[i] <= b && i<primeNum; i++, ans++);

        cout << ans << endl;
    }
    
    return 0;
}