\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

• Viết editorial lần 3 vì lỗi mà mất 2 bài :))

\(\color{orange}{\text{Hướng dẫn}}\)

• Mục tiêu:

Bước 1: Tìm các số nguyên tố

Bước 2: Chọn các cặp số nguyên tố \(A, B\) thỏa \(A + B \leq N\) và \(A + B\) cũng là số nguyên tố

Bước 3: Xuất ra các cặp số theo thứ tự từ điển

\(\color{goldenrod}{\text{Tiếp cận}}\)

• Bước 1

Kiểm tra số nguyên tố của một số \(n\) bất kì thì mất \(O(n), O(\sqrt{n})\) hoặc nhanh hơn tùy cách cài đặt

Kiểm tra số nguyên tố của \(n\) số \(1, 2, \cdots, n\) thì ta có thể dùng sàng để đạt được \(O(n log n), O(n log log n), O(n)\)

Sau khi sàng việc kiểm tra tính nguyên tố của một số chỉ mất \(O(log n)\) hoặc \(O(1)\) tùy cách cài đặt

• Bước 2

Duyệt qua các cặp \((A, B)\) với \(1 \leq A, B \leq n\) rồi kiểm tra tính nguyên tố của \(A, B, A + B\) sẽ mất \(O(n^2)\)

Gọi \(S\) là tập các số nguyên tố không lớn hơn \(n\)

Duyệt qua các cặp \((A, B)\) với \(A, B \in S\) rồi kiểm tra tính nguyên tố của \(A + B\) sẽ mất \(O(n + |S|^2)\)

Nhận xét:

• Vì \(A, B\) nguyên tố nên \(A + B\) nguyên tố khi và chỉ khi \(A\) chẵn hoặc \(B\) chẵn
• Không mất tính tổng quát, giả sử \(A \leq B\) thì ta có cặp \((A, B)\) thỏa mãn khi \(A = 2\), \(B \in S\), \(A + B \in S\)

Vậy ta chỉ cần duyệt qua các số nguyên tố \(P \in S\), và kiểm tra cặp \((P, P + 2)\) có thỏa mãn hay không. Cách này mất \(O(n + |S|)\)

• Bước 3

Sắp xếp các cặp nghiệm thỏa mãn và xuất ra, cách này thì \(O(n log n)\)

Nhận xét:

• việc lấy các số nguyên tố có thể lấy trong \(O(n)\) với thứ tự từ điển.
• Việc lấy các cặp nghiệm thỏa mãn có thẻ lấy trong \(O(|S|)\) vớ thứ tự từ điển

Vậy ta không cần sắp xếp mà có thể xuất ra cặp nghiệm trong \(O(|res|)\)

\(\color{green}{\text{Code tham khảo }}\): Approach

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n)\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>
#include <vector>

using namespace std;

vector<int> lpf; /// lowest prime factor   
vector<int> prime; /// prime list         | approx 80K numbers for first 1e6 numbers
vector<int> twinprime; /// twinprime list | approx 8K numbers for first 1e6 numbers

int sieve(int n)
{
    lpf.assign(n + 1, 2);
    prime.assign(1, 2);

    for (int x = 3; x <= n; x += 2)
    {
        if (lpf[x] == 2) /// (x) isnt multiple of any other prime than itself
        {
            lpf[x] = x; /// (x) is prime, its lowest prime factor is itself
            prime.push_back(x);

            if (lpf[x - 2] == x - 2) /// (x - 2) is also a prime
                twinprime.push_back(x - 2);
        }

        for (int t : prime)
        {
            if (t > lpf[x] || t * x > n) break;
            lpf[t * x] = t;
        }
    }
}

int main()
{
    int n;
    cin >> n;

    sieve(n);
    cout << twinprime.size() << '\n';
    for (int p : twinprime)
    {
        cout << 2 << ' ' << p << '\n';
    }

    return 0;
}