THREEPRIMES (Thi thử DHBB)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e7;

// Sàng nguyên tố
vector<bool> isPrime;
void sieve() {
    isPrime.assign(N + 1, true);
    isPrime[0] = false;
    isPrime[1] = false;

    for (int i = 2; i * i <= N; ++i) {
        if (isPrime[i] == true) {
            for (int j = i * i; j <= N; j += i)
                isPrime[j] = false;
        }
    }
}

// Giải bài toán - O(n^(1,367))
int query(int n) {
    for (int p = 2; p <= N; ++p)
        if (isPrime[p]) {
            if (isPrime[p * 2 - 1]) {
                if (--n == 0) {
                    cout << p << ' ' << p << ' ' << p * 2 - 1;
                    return 0;
                }
            }

            if (isPrime[p * 2 + 1]) {
                if (--n == 0) {
                    cout << p << ' ' << p << ' ' << p * 2 + 1;
                    return 0;
                }
            }
        }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    sieve();
    int n; cin >> n;
    query(n);

    return 0;
}

/*
#include <bits/stdc++.h>
using namespace std;

const int N = 1e7;

// Sàng nguyên tố tuyến tính - O(N)
vector<int> prime;
vector<int> lpf;
void sieve() {
    prime.assign(1, 2);
    lpf.assign(N + 1, 2);

    for (int x = 3; x <= N; x += 2) {
        if (lpf[x] == 2)
            prime.push_back(lpf[x] = x);

        for (int i = 0; i < prime.size() && prime[i] <= lpf[x] && prime[i] * x <= N; ++i)
            lpf[prime[i] * x] = prime[i];
    }
}

// Kiểm tra nguyên tố - O(1)
bool isPrime(int x) {
    return (x > 1) && (lpf[x] == x);
}

// Giải bài toán - O(n^(1,367))
int query(int n) {
    for (int p : prime) {
        if (isPrime(p * 2 - 1)) {
            if (--n == 0) {
                cout << p << ' ' << p << ' ' << p * 2 - 1;
                return 0;
            }
        }

        if (isPrime(p * 2 + 1)) {
            if (--n == 0) {
                cout << p << ' ' << p << ' ' << p * 2 + 1;
                return 0;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    sieve();
    int n; cin >> n;
    query(n);

    return 0;
}
*/