素数テーブル (prime_table)

目的

1～Nまでの素数を判定し、vector型に収納する。 素数であれば1を、合成数であれば0を返す。

オーダー

O(N log logN)

コード

vector<bool> prime_table(int n)
{
    vector<bool> prime(n + 1, true);
    if (n >= 0)
        prime[0] = false;
    if (n >= 1)
        prime[1] = false;
    for (int i = 2; i * i <= n; i++)
    {
        if (!prime[i])
            continue;
        for (int j = i + i; j <= n; j += i)
        {
            prime[j] = false;
        }
    }
    return prime;
}

コードテスト

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

vector<bool> prime_table(int n)
{
    vector<bool> prime(n + 1, true);
    if (n >= 0)
        prime[0] = false;
    if (n >= 1)
        prime[1] = false;
    for (int i = 2; i * i <= n; i++)
    {
        if (!prime[i])
            continue;
        for (int j = i + i; j <= n; j += i)
        {
            prime[j] = false;
        }
    }
    return prime;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll Q;
    cin >> Q;
    auto t=prime_table(10000); //10000までを判定

    cout << t.at(Q) << endl;
}

100
0

101
1

1
0

2
1

出典

ei1333.github.io