Kiểm tra số nguyên tố (VL11)

Nguồn: CLUE OJ Độ khó: Trung bình Vòng lặp Mã bài VL11

Đề bài

Cho số nguyên $n$ (có thể âm). Hãy kiểm tra $n$ có phải là số nguyên tố hay không.

Nhắc lại: số nguyên tố là số nguyên lớn hơn 1 chỉ có đúng hai ước dương là $1$ và chính nó. Vì vậy các số $\le 1$ (gồm $1$, $0$ và mọi số âm) đều không phải số nguyên tố.

Dữ liệu vào:

Một dòng chứa số nguyên $n$.

Kết quả:

In ra YES nếu $n$ là số nguyên tố, ngược lại in ra NO.

Giới hạn:

• $|n| \le 10^{12}$

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

Ví dụ 1 – input

7

Ví dụ 1 – output

YES

Giải thích:

• $7$ chỉ có hai ước dương là $1$ và $7$ nên là số nguyên tố.
• $-7$, $0$, $1$ không phải số nguyên tố (in NO).

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

Ý tưởng

Số nguyên tố phải ≥ 2, nên n ≤ 1 (kể cả số âm) in ngay NO. Với n ≥ 2, nếu n có ước d với 2 ≤ d và d·d ≤ n thì n là hợp số; nếu không có thì là số nguyên tố. Chỉ cần thử tới √n ≈ 10^6 lần.

Ví dụ n = 25: thử i = 2, 3, 4, 5 → 25 % 5 == 0 nên NO. Với n = 7: thử i = 2 (vì 3·3 > 7) → không chia hết → YES.

Lưu ý / bẫy thường gặp

• Quên xét n < 2: số 1, 0, số âm bị in YES.
• Lấy trị tuyệt đối số âm: -7 không phải số nguyên tố.
• Điều kiện i * i < n (thiếu dấu bằng) bỏ sót số chính phương như 25.
• Thử tới n - 1 thì quá chậm với n ≈ 10^{12}.
• n tới 10^{12} phải dùng long long (cả biến i vì i * i lớn).

Lời giải

Code chuẩn bên dưới đã chấm đúng toàn bộ 20 test trên CLUE OJ.

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 😇