Vị trí các số nguyên tố

Nguồn: CLUE OJ Độ khó: Dễ Mảng 1 chiều Kiểm tra số nguyên tố

Đề bài

Cho số nguyên dương $N$ và dãy số nguyên $A_1, A_2, \ldots, A_N$. Hãy tìm và in ra vị trí cùng giá trị của tất cả các phần tử là số nguyên tố, theo thứ tự từ trái sang phải. Vị trí được đánh số từ $1$.

Nhắc lại: số nguyên tố là số tự nhiên lớn hơn $1$ chỉ có hai ước dương là $1$ và chính nó. Vì vậy các số $0, 1$ và các số âm không phải số nguyên tố.

Dữ liệu vào:

• Dòng đầu là số nguyên dương $N$.
• Dòng thứ hai gồm $N$ số nguyên $A_1, A_2, \ldots, A_N$.

Kết quả:

• Mỗi phần tử là số nguyên tố in trên một dòng gồm hai số: vị trí và giá trị của nó.
• Nếu dãy không có số nguyên tố nào, in ra KHONG CO SO NGUYEN TO.

Giới hạn:

• $1 \le N < 1000$
• $|A_i| < 10^7$

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

5
1 2 3 5 6

Ví dụ 1 – output

2 2
3 3
4 5

Ví dụ 2 – input

5
4 6 8 10 12

Ví dụ 2 – output

KHONG CO SO NGUYEN TO

• Ví dụ 1: các số nguyên tố là $2$ (vị trí 2), $3$ (vị trí 3) và $5$ (vị trí 4); số $1$ và $6$ không phải số nguyên tố.
• Ví dụ 2: dãy toàn số chẵn lớn hơn 2 nên không có số nguyên tố nào.

Nguồn: phỏng theo bài "MẢNG 5.10" – vinhdinhcoder.net (chủ đề Mảng 1 chiều).

Lời mở đầu

Duyệt mảng và kiểm tra từng phần tử có phải số nguyên tố không. Có hai chỗ hay mất điểm: các số không phải nguyên tố "đặc biệt" (0, 1, số âm) và tốc độ – thử ước tới tận $x - 1$ với gần 1000 số cỡ $10^7$ là $10^{10}$ phép chia. Ghi chú: đề gốc cho $|A_i| < 10^7$ nên dãy có thể chứa số âm và số 0; theo định nghĩa, số nguyên tố là số tự nhiên lớn hơn 1, nên số âm (kể cả $-7$) không phải số nguyên tố.

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ộ test20 testÝ tưởngthử ước tới √xLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

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

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau.

Test	Nội dung kiểm tra
1–2	Hai ví dụ của đề (có và không có số nguyên tố)
3–6, 9	Số âm, 0, 1, số 2, dãy 1 phần tử – nhận 1 hay $-7$ là số nguyên tố là sai
7, 10, 15	Bình phương của số nguyên tố ($9, 25, \ldots, 961, 1369$) và tích hai số nguyên tố gần $\sqrt{10^7}$ – điều kiện i * i < x sai
8, 11–12, 15, 19	Rất nhiều số nguyên tố lớn gần $10^7$ – thử ước tới $x - 1$ bị quá thời gian
13–14, 16–18, 20	Dãy ngẫu nhiên 999 số, toàn số nguyên tố âm, dãy toàn số chẵn

Ý tưởngHàm kiểm tra nguyên tố chỉ thử ước tới căn x

Viết hàm laNguyenTo(x):

• $x < 2$ (gồm 0, 1 và mọi số âm) → không phải số nguyên tố.
• $x$ chẵn → chỉ có $x = 2$ là số nguyên tố.
• Thử các ước lẻ $i = 3, 5, 7, \ldots$ trong khi $i \cdot i \le x$; gặp ước thì không phải nguyên tố.

Vì sao chỉ cần tới √x?

Nếu $x = p \cdot q$ với $p \le q$ thì $p \cdot p \le p \cdot q = x$, tức $x$ luôn có một ước $\le \sqrt{x}$. Không tìm thấy ước nào $\le \sqrt{x}$ thì $x$ là số nguyên tố. Với $x < 10^7$ chỉ cần thử khoảng 1600 số lẻ thay vì $10^7$ số.

Trong main, duyệt $i = 1..N$; số nào nguyên tố thì in i a[i] và bật cờ coSo = true. Hết vòng mà cờ vẫn false thì in KHONG CO SO NGUYEN TO.

Em nhập dãy rồi bấm Tiếp để xem từng số được kiểm tra:

Dãy A =

Ví dụ nhanh:

Lời giảiHàm laNguyenTo + một cờ đánh dấu

$|A_i| < 10^7$ nên dùng int là đủ; i * i không quá $10^7$ nên cũng không tràn.

C++▶ Chạy tay từng dòng codeGọi hàm laNguyenTo cho từng phần tử.

Dữ liệu vào (stdin) – sửa thoải mái5 1 2 3 5 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Hàm trả về ngay khi biết kết quả (return giữa vòng lặp) nên hợp số dừng rất sớm; chỉ số nguyên tố mới phải thử hết tới √x.
2. Điều kiện là i * i <= x (có dấu bằng): với $x = 49$, phải thử tới $i = 7$ mới thấy ước.
3. Python dùng while i * i <= x với bước 2 – nhanh gấp đôi so với thử mọi số.

Không gian$O(N)$

Thời gian$O(N\sqrt{\max A_i})$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.007s. Bản Python đúng 20/20 test, chạy lâu nhất 0.157s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Thử ước từ 2 tới $x - 1$	16/20	sai test 11, 12, 15, 19
Quên loại 0, 1 và số âm	10/20	sai test 1, 3, 4, 6, 9, 13, 14, 16, 17, 19
Lấy trị tuyệt đối (coi $-7$ là số nguyên tố)	15/20	sai test 3, 9, 13, 14, 17
Điều kiện i * i < x (thiếu dấu bằng)	13/20	sai test 2, 7, 10, 14, 15, 16, 19
In vị trí đếm từ 0	6/20	sai test 1, 3, 4, 5, 8, 10, 11, 12, 13, 14, 15, 18, 19, 20

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

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.007s	Full điểm
	Python	20/20	0.157s	Full điểm
Thử tới x − 1	C++	16/20	–	Mất 4 test
Quên 0, 1, số âm	C++	10/20	–	Mất 10 test
Lấy |x|	C++	15/20	–	Mất 5 test
i*i < x	C++	13/20	–	Mất 7 test
Vị trí từ 0	C++	6/20	–	Mất 14 test

Ghi chú của mình: hàm kiểm tra số nguyên tố "thử ước tới căn" là đoạn code em sẽ dùng lại rất nhiều lần – hãy tự viết lại cho thuộc, nhớ kỹ hai dòng đầu: x < 2 và số chẵn.

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 😇