Spoiler Alert

Naive Approach

• Thử các cặp \((a, b)\) mà (\(a, b\) nguyên tố và \(2 \leq a, b \leq N\)) và tăng biến đếm khi \(a + b = n\)

Duyệt qua \(\forall 1 \leq a \leq b \leq n\)

Khởi tạo biến đếm = 0

Tăng biến đếm khi cả 3 điều kiện thỏa (\(a\) nguyên tố), (\(b\) nguyên tố), (\(a + b = n\))

Reference TLE code | \(O(n ^ 2) \times O(isPrime(x))\) time | \(O(isPrime())\) auxiliary space | Naive Brute-forces

bool isPrime(int x) { ... } /// return true <=> x la so nguyen to
int main()
{
    int n;
    cin >> n;
    int res = 0;
    for (int a = 1; a <= n; ++a)
        for (int b = a; b <= n; ++b)
            res += isPrime(a) && isPrime(b) && (a + b == n);

    cout << res;
    return 0;
}

Optimize Previous Approach

• Nhận thấy rằng \(a + b = n\) nên \(b = n - a\)

Với \(n\) là hằng số và \(a\) là các số trong đoạn \([2..\frac{n}{2}]\)

\(min_a\) thỏa \(a\) là số nguyên tố là 2

\(max_a\) đạt được khi \(a \leq b = \frac{n}{2} \Rightarrow n = a + \frac{n}{2} \Rightarrow a \leq \frac{n}{2}\)

Từ đây ta có \(a + b = a + (n - a) = n\) luôn thỏa

Khi này ta chỉ cần kiểm tra xem \(a\) và \(b = n - a\) có đồng thời nguyên tố thì tăng biến đếm

Reference TLE code | \(O(n) \times O(isPrime(x))\) time | \(O(isPrime())\) auxiliary space | Brute-forces

bool isPrime(int x) { ... } /// return true <=> x la so nguyen to
int main()
{
    int n;
    cin >> n;
    int res = 0;
    for (int a = 2; a <= n / 2; ++a)
        res += isPrime(a) && isPrime(n - a);

    cout << res;
    return 0;
}

Sieve Approach

• Nhận xét rằng việc kiểm tra phụ thuộc vào hàm kiểm tra \(isPrime()\)

Ta sẽ tiền xử lí (\(precal\)) lấy tất cả các số nguyên tố trong đoạn \([n, \frac{n}{2}]\)

• Gọi hàm \(checkPrime()\) là hàm kiểm tra số nguyên tố sau tiền xử lí. Hiển nhiên \(O(checkPrime()) \leq O(isPrime())\)

Lúc này đpt là \(O(precal) + O(query)\) với \(O(query) = O(n) \times O(checkPrime())\)

• Nếu ta sài \(Eratosthenes Sieve\) thì đpt là \(O(precal) = O(n \log(\log n))\)

*Optimize bằng \(Lowest\ Prime\ Factor\) để không xét lại các số đã xét và đạt đpt \(O(precal) = O(n)\)

• Nếu ta sài mảng nguyên tố \(prime[]\) và chặt nhị phân kiểm tra thì đpt là \(O(\log prime.size)\) (với \(prime\) là mảng nguyên tố)

*Optimize bằng mảng đánh dấu thì đpt là \(O(checkPrime()) = 1\)

• Sau đó ta chỉ cần duyệt qua các số và tăng biến đếm như cách trên, khi này \(O(query) = O(n) \times O(checkPrime())\)

*Optimize bằng các số nguyên tố \(a \in prime[]\) và kiểm tra \(b = n - a\) là số nguyên tố, \(O(query) = O(prime.size) = O(\frac{\log n}{\log(\log n)})\)

Reference AC code | \(O(n)\) precal time + \(O(\frac{\log n}{\log(\log n)})\) query time | \(O(n)\) auxiliary space | Sieve

vector<bool> isPrime; /// isPrime bool vector  isPrime[x] = true <=> x = prime
vector<int>  prime;   /// Prime vector:          prime[n] = (n+1)th prime
vector<int>  lpf;     /// Lowest Prime Factor:     lpf[x] = min prime divisors of x
void linear_sieve(int lim) {
    prime.assign(1, 2);
    lpf.assign(lim + 1, 2);

    for (int i = 3; i <= lim; i += 2) {
        if (lpf[i] == 2) prime.push_back(lpf[i] = i);
        for (int j = 0; j < int(prime.size()) && prime[j] <= lpf[i] && prime[j] * i <= lim; ++j)
            lpf[prime[j] * i] = prime[j];
    }

    isPrime.assign(lim + 1, false);
    for (int x : prime) isPrime[x] = true;
}

int main()
{
    int n = readInt();
    linear_sieve(n - 2);

    int res = 0;
    for (int a : prime)
    {
        if (a > n / 2) break;
        res += isPrime[n - a];
    }

    cout << res;
    return 0;
}