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

• View this file on GitHub
• Last update: 2026-08-10 11:04:56+00:00
• Problem: https://judge.yosupo.jp/problem/enumerate_primes

Depends on

• Enumerate Primes (素数列挙) (math/number-theory/enumerate-primes.hpp)
• Prime Table (素数テーブル) (math/number-theory/prime-table.hpp)

Code

// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_primes
// clang-format on

#include <iostream>
#include <vector>

#include "../../math/number-theory/enumerate-primes.hpp"

using namespace std;

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  auto d = enumerate_primes(N);
  vector<int> ans;
  for (int i = B; i < static_cast<int>(d.size()); i += A) {
    ans.emplace_back(d[i]);
  }
  cout << d.size() << " " << ans.size() << "\n";
  for (int i = 0; i < static_cast<int>(ans.size()); i++) {
    if (i > 0) cout << " ";
    cout << ans[i];
  }
  cout << "\n";
}

#line 1 "test/verify/yosupo-enumerate-primes.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_primes
// clang-format on

#include <iostream>
#include <vector>

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

#include <algorithm>
#line 5 "math/number-theory/enumerate-primes.hpp"

#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;
}
#line 9 "test/verify/yosupo-enumerate-primes.test.cpp"

using namespace std;

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  auto d = enumerate_primes(N);
  vector<int> ans;
  for (int i = B; i < static_cast<int>(d.size()); i += A) {
    ans.emplace_back(d[i]);
  }
  cout << d.size() << " " << ans.size() << "\n";
  for (int i = 0; i < static_cast<int>(ans.size()); i++) {
    if (i > 0) cout << " ";
    cout << ans[i];
  }
  cout << "\n";
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	1_00	AC	2 ms	4 MB
g++	2_00	AC	2 ms	4 MB
g++	499477801_00	AC	4171 ms	167 MB
g++	499999993_00	AC	4123 ms	167 MB
g++	example_00	AC	2 ms	4 MB
g++	max_00	AC	4146 ms	167 MB
g++	max_01	AC	4142 ms	167 MB
g++	ten_00	AC	584 ms	38 MB
g++	ten_01	AC	86 ms	13 MB
g++	ten_02	AC	12 ms	4 MB
clang++	1_00	AC	2 ms	4 MB
clang++	2_00	AC	2 ms	4 MB
clang++	499477801_00	AC	2945 ms	167 MB
clang++	499999993_00	AC	2974 ms	167 MB
clang++	example_00	AC	2 ms	4 MB
clang++	max_00	AC	3035 ms	167 MB
clang++	max_01	AC	3024 ms	167 MB
clang++	ten_00	AC	427 ms	38 MB
clang++	ten_01	AC	83 ms	13 MB
clang++	ten_02	AC	11 ms	4 MB

Back to top page