← Real problems

ccc19s2

easymathsieveStatement on DMOJ

CP Lang

6 lineschecks
// ccc19s2 Pretty Average Primes: two primes averaging n.
let sieve = Sieve(2_000_000)
@!multitest
let n = read<4..=1_000_000>()
let p = (2..=n).find(p => sieve.is_prime(p) and sieve.is_prime(2 * n - p))!
print(p, 2 * n - p)

Accepted C++

77 lines · 0.24 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...) 1412
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 2e6 + 5;

bool prime[maxn + 1];
vector<int> primes;

void pcomp() {
	memset(prime, 1, sizeof(prime));
	prime[0] = prime[1] = false;
	for (int i = 2; i <= maxn; i++) {
		if (!prime[i]) {
			continue;
		}
		primes.push_back(i);
		if (i <= maxn / i) {
			for (int j = i * i; j <= maxn; j += i) {
				prime[j] = false;
			}
		}
	}
}

void solve() {
	int n;
	cin >> n;
	n *= 2;
	for (auto& a : primes) {
		if (binary_search(begin(primes), end(primes), n - a)) {
			cout << a << " " << n - a << endl;
			return;
		}
	}
}

int main() {
	pcomp();
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	int t = 1;
	cin >> t;
	for (int _ = 1; _ <= t; _++) {
		dbg(_);
		// cout << "Case #" << _ << ": ";
		solve();
	}
}