Giả thuyết Goldbach

Nguồn: Tin học trẻ bảng B thành phố Đà Nẵng năm 2021 – 2022 (Bài 3) Độ khó: Dễ Sàng Eratosthenes

Đề bài

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$ và $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.

Giới hạn: có $50\%$ test ứng với $x \le 10^3$; $30\%$ test ứng với $10^3 < x \le 10^4$; $20\%$ test ứng với $10^4 < x \le 10^6$. Thời gian 1 giây, bộ nhớ 256 MB.

Ví dụ – GOL.INP

10

Ví dụ – GOL.OUT

2

Giải thích ví dụ: $10 = 3 + 7 = 5 + 5$, có 2 cách ($7 + 3$ trùng với $3 + 7$ nên không tính thêm).

Lưu ý nộp bài: trên CLUE OJ bài này đọc/ghi qua tệp GOL.INP / GOL.OUT. Trong code mình dùng if (fopen("GOL.INP", "r")) { freopen(...); freopen(...); }: có tệp thì đọc tệp, không có thì tự động đọc từ bàn phím.

Lời mở đầu

Đây là bài "nhập môn" rất đẹp về số nguyên tố: chỉ cần duyệt số nhỏ $a$ của cặp, số còn lại là $b = x - a$, rồi kiểm tra cả hai có nguyên tố không. Điểm mấu chốt là kiểm tra nguyên tố thật nhanh. Mình đi từ cách thử chia từng số, tới cách sàng Eratosthenes một lần dùng mãi.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 test, 3 mứcÝ tưởnga ≤ x − aCách 1thử chiaCách 2sàng EratosthenesTổng kếtkết quả chạy thật

Bộ testBộ test chính thức có gì?

Test	x	Đáp án
1–50	6 – 992	1 – 48
51–80	1.028 – 9.498	18 – 187
81–100	10.486 – 129.964	134 – 2389

• Các nhóm test khớp đúng 3 mức giới hạn của đề. Riêng nhóm cuối, $x$ lớn nhất trong bộ test chỉ khoảng $1{,}3 \cdot 10^5$ (đề cho phép tới $10^6$) – lời giải của mình vẫn tính cho trường hợp $10^6$.
• Test nhỏ nhất là $x = 6 = 3 + 3$, đáp án $1$.

Ý tưởngDuyệt số nhỏ hơn trong cặp

Mỗi cách phân tích $x = a + b$ ta luôn viết sao cho $a \le b$, tức là $a \le x/2$. Khi đó mỗi cách được đếm đúng một lần:

Đáp án

$$m = \#\{\, a \;:\; 2 \le a \le x/2,\ a \text{ nguyên tố},\ x - a \text{ nguyên tố} \,\}$$

Em nhập $x$ (chẵn, nhỏ hơn 300 để dễ xem) rồi bấm Tiếp để xem từng cặp $(a, x - a)$ được kiểm tra:

x =

Ví dụ nhanh:

Cách 1Thử chia tới căn để kiểm tra nguyên tố

Viết hàm laNT(v) thử chia $v$ cho $2, 3, \ldots, \lfloor\sqrt{v}\rfloor$. Với mỗi $a$ từ $2$ tới $x/2$, nếu laNT(a) và laNT(x - a) thì tăng biến đếm.

C++▶ Chạy tay từng dòng codeCách 1: với mỗi a ≤ x/2, kiểm tra a và x − a bằng hàm thử chia laNT.

Dữ liệu vào (stdin) – sửa thoải mái10

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Nhờ toán tử && "ngắt sớm", khi laNT(a) sai thì không cần kiểm tra x - a.
• Số phép chia tối đa khoảng $\frac{x}{2} \cdot \sqrt{x}$: với $x = 10^6$ là $5 \cdot 10^8$ trong trường hợp xấu nhất, nhưng thực tế phần lớn số bị loại rất sớm (chia hết cho 2, 3, 5…) nên vẫn nhanh.

Không gian$O(1)$

Thời gian$O(x \sqrt{x})$

Kết quả chạy thật: bản C++ đúng 100/100 test (nhóm 1: 50/50, nhóm 2: 30/30, nhóm 3: 20/20), lâu nhất 0,011s; bản Python đúng 100/100 (nhóm 1: 50/50, nhóm 2: 30/30, nhóm 3: 20/20), lâu nhất 0,219s.

Cách 2Sàng Eratosthenes tới x

Thay vì kiểm tra từng số, ta sàng một lần: đánh dấu mọi số $\le x$ là nguyên tố, rồi với mỗi $i$ nguyên tố (từ $2$ tới $\sqrt{x}$) gạch bỏ các bội $i^2, i^2 + i, \ldots$. Sau đó tra nt[a] và nt[x - a] trong $O(1)$.

C++▶ Chạy tay từng dòng codeCách 2: sàng Eratosthenes tới x rồi đếm các a ≤ x/2 có nt[a] và nt[x − a].

Dữ liệu vào (stdin) – sửa thoải mái10

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Sàng tốn $O(x \log \log x)$, sau đó vòng đếm chỉ $x/2$ lần tra mảng – với $x = 10^6$ chạy chỉ vài mili giây.
• Bắt đầu gạch từ $i^2$ vì các bội nhỏ hơn ($2i, 3i, \ldots$) đã bị gạch bởi các số nguyên tố nhỏ hơn $i$.
• Bản Python gạch cả dãy bội bằng một phép gán lát cắt nt[i*i::i] = bytes(...) – nhanh hơn vòng for rất nhiều.

Không gian$O(x)$

Thời gian$O(x \log \log x)$

Kết quả chạy thật: bản C++ đúng 100/100 test, lâu nhất 0,015s; bản Python đúng 100/100, lâu nhất 0,040s.

Tổng kếtKết quả chạy thật trên bộ test

Mình chấm cả 2 cách (C++ và Python) trên toàn bộ 100 test với giới hạn 1 giây, đo thời gian CPU:

Lời giải	$x \le 10^3$ test 1–50	$x \le 10^4$ test 51–80	$x \le 10^6$ test 81–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	50/50	30/30	20/20	100/100	0,011s
Cách 1 – Python	50/50	30/30	20/20	100/100	0,219s
Cách 2 – C++	50/50	30/30	20/20	100/100	0,015s
Cách 2 – Python	50/50	30/30	20/20	100/100	0,040s

Ghi chú của mình: với bộ test này ($x \le 1{,}3 \cdot 10^5$) cả hai cách đều qua, nhưng sàng Eratosthenes mới là cách "chuẩn": khi cần kiểm tra nguyên tố cho rất nhiều số trong một đoạn, hãy sàng một lần rồi tra mảng. Thử chia chỉ hợp lý khi kiểm tra ít số.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇