Nguyên tố kép

Nguồn: Đề tuyển sinh lớp 10 Trường Phổ thông Năng khiếu 2013 – 2014 (Bài 1) Độ khó: Trung bình Số nguyên tố Phân tích thừa số

Đề bài

Một số nguyên dương $M$ được gọi là số nguyên tố kép nếu có thể biểu diễn $M$ dưới dạng tích của hai số nguyên tố khác nhau.

Hãy xác định số nguyên tố kép $M$ lớn nhất không vượt quá giá trị nguyên dương $N$ cho trước.

Dữ liệu vào: từ tệp văn bản PRIME.INP chỉ chứa 1 số nguyên dương $N$ với $6 \le N \le 10^9$.

Dữ liệu ra: ghi ra tệp văn bản PRIME.OUT giá trị $M$ tìm được.

Giới hạn: thời gian 1 giây, bộ nhớ 256 MB.

Ví dụ – PRIME.INP

17

Ví dụ – PRIME.OUT

15

Giải thích ví dụ: $17$ là số nguyên tố, $16 = 2^4$ không phải tích hai số nguyên tố khác nhau, còn $15 = 3 \cdot 5$ là số nguyên tố kép. Lưu ý $9 = 3 \cdot 3$ không phải số nguyên tố kép vì hai thừa số trùng nhau.

Lưu ý nộp bài: trên CLUE OJ bài này đọc/ghi qua tệp PRIME.INP / PRIME.OUT. Code C++ dùng if (fopen("PRIME.INP", "r")) { freopen(...); freopen(...); }: có tệp thì đọc tệp, không có thì đọc bàn phím, nộp ở đâu cũng được. Bản Python làm tương tự với os.path.exists("PRIME.INP").

Lời mở đầu

Cách nghĩ "liệt kê mọi tích $p \cdot q$" rất tự nhiên nhưng với $N = 10^9$ thì có quá nhiều số nguyên tố. Mẹo của bài là nhận ra số nguyên tố kép rất dày: đi lùi từ $N$ xuống, chỉ vài bước là gặp ngay. Việc còn lại là kiểm tra nhanh "$M$ có phải tích hai số nguyên tố khác nhau không".

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Ý tưởngthừa số nhỏ nhấtCách 1sàng + thử mọi cặpCách 2đi lùi từ NTổng kếtkết quả chạy thật

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

Đề không chia subtask, mình chia 100 test thành 4 nhóm theo độ lớn của $N$ để tiện so sánh:

Nhóm	Test	N	Đáp án M	N − M (lớn nhất)	Số test có M = N
1	1 – 20	8 … 33.765	6 … 33.763	10	8
2	21 – 50	1.321 … 132.033	1.318 … 132.031	17	4
3	51 – 80	102.851 … 10.032.311	102.849 … 10.032.311	22	5
4	81 – 100	500.004.671 … 1.000.000.000	500.004.671 … 999.999.991	25	3

• Cột "N − M" cho thấy: ở mọi test, đáp án chỉ cách $N$ tối đa 25 đơn vị. Đây chính là cơ sở của cách 2.
• Test 100 là $N = 10^9$, đáp án $999\,999\,991 = 67 \cdot 14\,925\,373$.

Ý tưởngKiểm tra M = p · q bằng thừa số nguyên tố nhỏ nhất

Gọi $p$ là ước nguyên tố nhỏ nhất của $M$ (tìm bằng thử chia $p = 2, 3, \ldots$ khi $p^2 \le M$). Nếu $M = p \cdot q$ với $p < q$ nguyên tố thì $p$ chắc chắn là ước nhỏ nhất đó, và $q = M / p$. Vậy:

Điều kiện

$M$ là số nguyên tố kép ⇔ $M$ có ước $p$ nhỏ nhất với $p^2 \le M$, và $q = M/p$ là số nguyên tố, $q \ne p$.

Nếu không tìm được $p$ nào với $p^2 \le M$ thì $M$ là số nguyên tố, không phải số nguyên tố kép. Ví dụ $M = 16$: $p = 2$, $q = 8$ không nguyên tố → loại. $M = 9$: $p = 3$, $q = 3 = p$ → loại. $M = 15$: $p = 3$, $q = 5$ nguyên tố, khác $3$ → nhận.

Vì số nguyên tố kép rất dày (trong 100 số liên tiếp quanh $10^9$ luôn có khá nhiều), ta chỉ cần đi lùi từ $N$ và kiểm tra từng số. Em nhập $N$ rồi bấm Tiếp để xem từng số được kiểm tra:

N =

Ví dụ nhanh:

Cách 1Sàng nguyên tố + thử mọi cặp p < q

Thừa số nhỏ nhất ít nhất là $2$ nên thừa số lớn $q \le N/2$. Sàng Eratosthenes các số nguyên tố tới $N/2$, rồi thử mọi cặp $p < q$ có $p \cdot q \le N$ (vòng trong dừng ngay khi tích vượt $N$), giữ tích lớn nhất.

C++▶ Chạy tay từng dòng codeCách 1: sàng nguyên tố tới N/2, thử mọi cặp p < q với p·q ≤ N, giữ tích lớn nhất.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Khi $N = 10^9$ phải sàng tới $5 \cdot 10^8$: bản C++ dùng vector<bool> (khoảng 60 MB) nhưng sàng không kịp 1 giây; bản Python cần mảng 500 MB, vượt luôn bộ nhớ.
• Vòng thử cặp dừng sớm nhờ break, nên số cặp thực sự xét không lớn: với $N \le 10^7$ (nhóm 1–3) bản C++ chỉ chạy tối đa 0,06 giây. Nhưng $N$ cỡ $10^9$ thì riêng phần sàng đã không kịp.

Không gian$O(N)$

Thời gian$O(N \log\log N + \text{số cặp})$

Kết quả chạy thật: bản C++ đúng 80/100 test (Nhóm 1: 20/20, Nhóm 2: 30/30, Nhóm 3: 30/30, Nhóm 4: 0/20), test đúng chạy lâu nhất 0,059 giây; 20 test quá thời gian; bản Python đúng 60/100 test (Nhóm 1: 20/20, Nhóm 2: 30/30, Nhóm 3: 10/30, Nhóm 4: 0/20), test đúng chạy lâu nhất 0,089 giây; 40 test quá thời gian.

Cách 2Đi lùi từ N, kiểm tra bằng thừa số nhỏ nhất – Full điểm

Hàm laNTKep(m) tìm ước nhỏ nhất $p$ bằng thử chia; gặp được thì trả lời ngay "$m/p$ nguyên tố và khác $p$ không?". Vòng chính đi lùi từ $N$ cho tới khi gặp số nguyên tố kép đầu tiên.

C++▶ Chạy tay từng dòng codeCách 2: m đi lùi từ N; với mỗi m tìm ước nhỏ nhất p, kiểm tra q = m/p nguyên tố và q ≠ p.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mỗi lần kiểm tra tốn tối đa $O(\sqrt m)$ (khoảng $31\,623$ bước với $m \approx 10^9$) – nhưng chỉ khi $m$ nguyên tố hoặc có ước nhỏ nhất lớn. Phần lớn các số có ước nhỏ nên dừng rất sớm.
• Theo bộ test, đáp án cách $N$ tối đa 25 đơn vị, nên tổng cộng chỉ vài chục lần kiểm tra.
• Dùng long long cho p * p để không tràn khi $m$ gần $10^9$.

Không gian$O(1)$

Thời gian$O(k \sqrt N)$, $k$ = số bước lùi (rất nhỏ)

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

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	Nhóm 1 test 1–20	Nhóm 2 test 21–50	Nhóm 3 test 51–80	Nhóm 4 test 81–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	20/20	30/30	30/30	0/20	80/100	0,059s
Cách 1 – Python	20/20	30/30	10/30	0/20	60/100	0,089s
Cách 2 – C++	20/20	30/30	30/30	20/20	100/100	0,005s
Cách 2 – Python	20/20	30/30	30/30	20/20	100/100	0,030s

Ghi chú của mình: cả 2 cách đều cho đáp án đúng ở mọi test chạy kịp. Cách 1 (sàng + thử cặp) mất trọn nhóm 4 vì phải sàng tới $N/2 = 5 \cdot 10^8$. Cách 2 chỉ đi lùi tối đa 25 bước trên bộ test, mỗi bước thử chia tới $\sqrt N$, nên cả C++ lẫn Python đều chạy gần như tức thì. Bài học: thay vì sinh tất cả ứng viên, hãy đi lùi từ N và kiểm tra nhanh từng số – rất hiệu quả khi các số cần tìm "dày" như số nguyên tố kép.

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 😇