---
tags: Coding
---
# 質數建表
**埃拉托斯特尼篩法**
複雜度O(n log logn)

i*i的部分要注意有沒有超過int的範圍。
如果N超過10^5，int要用long long

#define int long long

vector<bool> a(N);
vector<int> prime;
for(int i=0;i<N;i++)a[i]=false;
for(int i=2;i<N;i++){
    if(!a[i]){
        prime.push_back(i);
        if((i*i)<N){// 也可以用i <= sqrt(N) 避免 i * i 溢出 
            for(int j=i*i;j<N;j+=i){
                a[j]=1;
            }
        }
    }
}

**歐拉篩法**
複雜度O(n)

void eulerSieve(int N) {
    vector<int> prime;
    vector<bool> arr(N, false);

    for (int i = 2; i < N; ++i) {
        if (!arr[i]) {
            prime.push_back(i);  // i 是質數
        }
        for (int p : prime) {
            if (i * p >= N) break;
            arr[i * p] = true;  // 標記合數
            if (i % p == 0) break;  // 確保每個合數只被最小質因數篩掉一次
        }
    }
}

## 範例
### uva10539
https://vjudge.net/problem/UVA-10539
找一個範圍內almost prime
almost prime是因數只有一個質數的數
也就是質數的每個次方
EX:
3\^1
3\^2
3\^3

#include <bits/stdc++.h>
#define int long long
#define all(vec) vec.begin(), vec.end()
using namespace std;

const int N = 1000005;
vector<bool> arr(N, 0);
vector<int> prime;
vector<int> ap;

//法一 使用埃拉托斯特尼篩法生成質數
void buildPrime() {
    for (int i = 2; i < N; i++) {
        if (!arr[i]) {
            prime.push_back(i);
            if (i * i < N) {
                for (int j = i * i; j < N; j += i) {
                    arr[j] = 1;
                }
            }
        }
    }
}
// 法二 使用歐拉篩法生成質數
vector<bool> isprime(N + 1, true);
void buildPrime2() {
    isprime[0] = isprime[1] = false;
    for (int i = 2; i <= N; i++) {
        if (isprime[i]) prime.push_back(i);
        for (int j = 0; j < prime.size() && i * prime[j] <= N; j++) {
            isprime[i * prime[j]] = false;
            if (i % prime[j] == 0) break;  // 提前退出
        }
    }
}

void buildAlmostP() {
    for (int i = 0; i < prime.size(); i++) {
        for (long long j = prime[i] * prime[i]; j < 1e12; j *= prime[i]) {
            ap.push_back(j);
        }
    }
    sort(all(ap));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    long long n, l, r;
    buildPrime2();//看要用法一還是法二
    buildAlmostP();
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> l >> r;
        cout << upper_bound(all(ap), r) - lower_bound(all(ap), l) << endl;
    }
    return 0;
}