素数列挙 (Math/enumerate_primes.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-09-30 19:12:18+09:00
• Include: #include "Math/enumerate_primes.hpp"

enumerate_primes

vector<long long> enumerate_primes(long long n)

エラトステネスの篩によってn以下の素数を計算し、返します。

制約

• $0 \lt n$

計算量

• $O(n \log \log n)$

Verified with

• test/Math/enumerate_primes/yosupo-enumerate_primes.test.cpp

Code

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

vector<long long> enumerate_primes(long long n)
{
    assert(0 < n);

    vector<long long> primes;
    vector<bool> isChecked(n + 1, false);
    isChecked[0] = isChecked[1] = true;
    for (long long i = 2; i <= n; i++)
    {
        if (isChecked[i])
        {
            continue;
        }

        primes.push_back(i);
        isChecked[i] = true;

        for (long long j = i * i; j <= n; j += i)
        {
            if (!isChecked[j])
            {
                isChecked[j] = true;
            }
        }
    }

    return primes;
}

#line 1 "Math/enumerate_primes.hpp"
#include <bits/stdc++.h>
using namespace std;

vector<long long> enumerate_primes(long long n)
{
    assert(0 < n);

    vector<long long> primes;
    vector<bool> isChecked(n + 1, false);
    isChecked[0] = isChecked[1] = true;
    for (long long i = 2; i <= n; i++)
    {
        if (isChecked[i])
        {
            continue;
        }

        primes.push_back(i);
        isChecked[i] = true;

        for (long long j = i * i; j <= n; j += i)
        {
            if (!isChecked[j])
            {
                isChecked[j] = true;
            }
        }
    }

    return primes;
}

Back to top page