Giả thuyết Goldbach (THTB Đà Nẵng 2022)

Xem PDF

Điểm: 300 Thời gian: 1.0s Bộ nhớ: 256M Input: gol.inp Output: gol.out

Giả thuyết Goldbach do nhà toán học người Đức Christian Goldbach (1690-1764) nêu ra vào năm 1742 trong một lá thư gửi tới nhà toán học Leonhard Euler, là một trong những bài toán lâu đời và nổi tiếng còn chưa giải được trong lý thuyết số nói riêng và toán học nói chung. Giả thuyết phỏng đoán rằng:

Mỗi số tự nhiên chẵn lớn hơn \(2\) có thể biểu diễn bằng tổng của hai số nguyên tố.

Giả thuyết đã được chỉ ra là đúng tới \(4 \times 10^{18}\), nhưng hiện nay vẫn chưa được chứng minh hoàn toàn.

Bằng kiến thức tin học em hãy thực hiện thử thách sau: Cho trước số \(x\) là số tự nhiên chẵn lớn hơn \(2\).

Yêu cầu: Hãy cho biết có bao nhiêu cách phân tích số \(x\) thành tổng của 2 số nguyên tố.

Lưu ý: Nếu phân tích được \(x = a + b\) hay \(x = b + a\) (trong đó \(a\)\(b\) là các số nguyên tố) thì cũng chỉ được tính là một cách phân tích.

Input

  • Đọc ở file văn bản GOL.INP một số \(x\) là số tự nhiên chẵn lớn hơn \(2\).

Output

  • Ghi ra file văn bản GOL.OUT một số \(m\) theo yêu cầu.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(x \le 10^3\).
  • Subtask \(2\) (\(30\%\) số điểm): \(10^3 < x \le 10^4\).
  • Subtask \(3\) (\(20\%\) số điểm): \(10^4 < x \le 10^6\).

Example

Test 1

Input
10
Output
2
Note

\(10 = 3 + 7 = 5 + 5\)


Bình luận