test/math/prime-enumerate/yosupo-Enumerate-Primes.test.cpp

• View this file on GitHub
• Last update: 2023-12-03 13:41:56+08:00
• Problem: https://judge.yosupo.jp/problem/enumerate_primes

Depends on

• library/math/prime-enumerate.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_primes"

#include <iostream>

#include <vector>

#include "../../../library/math/prime-enumerate.hpp"

using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, a, b;
	cin >> n >> a >> b;
	auto primes = prime_enumerate(n);
	vector<int> ans;
	for(int i = 0; a * i + b < (int) primes.size(); i++) {
		ans.push_back(primes[a * i + b]);
	}
	cout << primes.size() << " " << ans.size() << "\n";
	for(auto x : ans) {
		cout << x << " \n"[x == ans.back()];
	}
	return 0;
}

#line 1 "test/math/prime-enumerate/yosupo-Enumerate-Primes.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_primes"

#include <iostream>

#include <vector>

#line 3 "library/math/prime-enumerate.hpp"
#include <cmath>


namespace felix {

// 2, 3, 5, 7, ...

std::vector<int> prime_enumerate(int N) {
	std::vector<bool> sieve(N / 3 + 1, 1);
	for(int p = 5, d = 4, i = 1, sqn = std::sqrt(N); p <= sqn; p += d = 6 - d, i++) {
		if(!sieve[i]) {
			continue;
		}
		for(int q = p * p / 3, r = d * p / 3 + (d * p % 3 == 2), s = 2 * p, qe = sieve.size(); q < qe; q += r = s - r) {
			sieve[q] = 0;
		}
	}
	std::vector<int> ret{2, 3};
	for(int p = 5, d = 4, i = 1; p <= N; p += d = 6 - d, i++) {
		if(sieve[i]) {
			ret.push_back(p);
		}
	}
	while(!ret.empty() && ret.back() > N) {
		ret.pop_back();
	}
	return ret;
}

} // namespace felix

#line 6 "test/math/prime-enumerate/yosupo-Enumerate-Primes.test.cpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, a, b;
	cin >> n >> a >> b;
	auto primes = prime_enumerate(n);
	vector<int> ans;
	for(int i = 0; a * i + b < (int) primes.size(); i++) {
		ans.push_back(primes[a * i + b]);
	}
	cout << primes.size() << " " << ans.size() << "\n";
	for(auto x : ans) {
		cout << x << " \n"[x == ans.back()];
	}
	return 0;
}

Back to top page