Enumerate Primes (素数列挙) (math/number-theory/enumerate-primes.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-08-10 07:26:44+00:00
• Include: #include "math/number-theory/enumerate-primes.hpp"

エラトステネスの篩を用いて素数を列挙します。

enumerate_primes

vector< int > enumerate_primes(int n)

$n$ 以下の素数を昇順に返します。

制約

• $0 \le n$

計算量

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

Depends on

• Prime Table (素数テーブル) (math/number-theory/prime-table.hpp)

Verified with

• test/verify/yosupo-enumerate-primes.test.cpp

Code

#pragma once

#include <algorithm>
#include <vector>

#include "prime-table.hpp"

std::vector<int> enumerate_primes(int n) {
  if (n <= 1) return {};
  auto d = prime_table(n);
  std::vector<int> primes;
  primes.reserve(std::count(d.begin(), d.end(), true));
  for (int i = 0; i < d.size(); i++) {
    if (d[i]) primes.push_back(i);
  }
  return primes;
}

#line 2 "math/number-theory/enumerate-primes.hpp"

#include <algorithm>
#include <vector>

#line 2 "math/number-theory/prime-table.hpp"

#line 4 "math/number-theory/prime-table.hpp"

/**
 * @brief Prime Table(素数テーブル)
 *
 */
std::vector<bool> prime_table(int n) {
  std::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;
}
#line 7 "math/number-theory/enumerate-primes.hpp"

std::vector<int> enumerate_primes(int n) {
  if (n <= 1) return {};
  auto d = prime_table(n);
  std::vector<int> primes;
  primes.reserve(std::count(d.begin(), d.end(), true));
  for (int i = 0; i < d.size(); i++) {
    if (d[i]) primes.push_back(i);
  }
  return primes;
}

Back to top page