Số số nguyên tố nhỏ nhất có tổng bằng N

2017-07-21
Bài gốc

Codeforces 735D

Đề bài

Cho số nguyên N > 0, tìm số số nguyên tố nhỏ nhất có tổng bằng N.

Giới hạn:

  • 2 ≤ n ≤ 2·109
Định dạng test

Input:

  • Một dòng duy nhất là số N.

Output:

  • Số số nguyên tố nhỏ nhất có tổng bằng N.

Ví dụ:

27
---
3

(27 = 2 + 2 + 23)

Thuật toán

Với N = 1, bài toán không có lời giải.

Nếu N là số nguyên tố, cách phân tích tối ưu là N = N, đáp số là 1.

Nếu N chẵn và N > 2, theo giả thuyết Goldbach: có thể biểu diễn N thành tổng của hai số nguyên tố, điều này được chứng minh đúng với N ≤ 4·1018.

Nếu N lẻ:

  • Các số nguyên tố > 2 là số lẻ, tổng của các số lẻ là số chẵn => trong cách phân tích N thành tổng các số nguyên tố, phải có một số nguyên tố chẵn, mà 2 là số nguyên tố chẵn duy nhất => N = 2 + (N-2). Đến đây, nếu (N-2) là số nguyên tố, thì đáp số là 2. Ngược lại:
  • Phân tích N = 3 + (N-3), N-3 là một số chẵn, lại theo giả thuyết Goldbach, N-3 là tổng của 2 số nguyên tố => kết quả là 3.
Source code

Ngôn ngữ: C++.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

bool isPrime(int x) {
    if (x == 1) return false;
    if (x == 2 || x == 3) return true;
    if (x % 2 == 0 || x % 3 == 0) return false;
    for(int i = 3; i <= sqrt(x); i += 2)
        if (x % i == 0) return false;
    return true;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n; cin >> n;

    if (isPrime(n)) cout << 1;
    else if (n % 2 == 0) cout << 2;
    else if (isPrime(n-2)) cout << 2;
    else cout << 3;

    return 0;
}
Độ phức tạp

O(√n)