test/math/prime.test.cpp

• View this file on GitHub
• Last update: 2025-10-26 10:54:48+08:00
• Problem: https://judge.yosupo.jp/problem/enumerate_primes

Depends on

• src/math/prime.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_primes
#include <bits/stdc++.h>
#define PUSHB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;

constexpr int MAXN = 5e8 + 5;
#include "../../src/math/prime.hpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  init_prime_table();
  int n, a, b;
  cin >> n >> a >> b;
  int ptr = upper_bound(ALL(primes), n) - primes.begin();
  int m = (ptr - b + a - 1) / a;
  cout << ptr << " " << m << "\n";
  for (int i = 0; a * i + b < ptr; i++) {
    cout << primes[a * i + b] << " \n"[i + 1 == m];
  }
  return 0;
}

#line 1 "test/math/prime.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_primes
#include <bits/stdc++.h>
#define PUSHB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;

constexpr int MAXN = 5e8 + 5;
#line 1 "src/math/prime.hpp"
vector<int> primes;
bitset<MAXN> isprime;
void init_prime_table() {
  isprime.set();
  isprime[0] = isprime[1] = false;
  for (int i = 2; i < MAXN; i++) {
    if (isprime[i]) primes.PUSHB(i);
    for (int p : primes) {
      if (i * p >= MAXN) break;
      isprime[i * p] = false;
      if (i % p == 0) break;
    }
  }
}
#line 9 "test/math/prime.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  init_prime_table();
  int n, a, b;
  cin >> n >> a >> b;
  int ptr = upper_bound(ALL(primes), n) - primes.begin();
  int m = (ptr - b + a - 1) / a;
  cout << ptr << " " << m << "\n";
  for (int i = 0; a * i + b < ptr; i++) {
    cout << primes[a * i + b] << " \n"[i + 1 == m];
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	1_00	AC	2093 ms	196 MB
g++	2_00	AC	2104 ms	197 MB
g++	499477801_00	AC	2116 ms	197 MB
g++	499999993_00	AC	2137 ms	197 MB
g++	example_00	AC	2117 ms	196 MB
g++	max_00	AC	2172 ms	196 MB
g++	max_01	AC	2156 ms	196 MB
g++	ten_00	AC	2140 ms	196 MB
g++	ten_01	AC	2140 ms	197 MB
g++	ten_02	AC	2157 ms	197 MB

Back to top page