Bài 1. Số nguyên tố (CHECKNT6K)
Ý tưởng
Khi kiểm tra $n$ có phải là số nguyên tố hay không, ta biết:
- Mọi số chẵn $> 2$ không thể là số nguyên tố (vì chia hết cho 2)
- Mọi số chia hết cho $3 > 3$ không thể là số nguyên tố (vì chia hết cho 3)
$\Rightarrow$ với $n > 3$ là số nguyên tố thì số đó không được chia hết cho $[2, 3] = 6$
\[\begin{align*} &6 \mid n \\[1mm] \Rightarrow \quad &n = 6q + r, \quad 0 \leq r < 6 \\[1mm] \Rightarrow \quad &r \in \{0, 1, 2, 3, 4, 5\} \\ \end{align*}\]Biện luận số dư:
$r = 0 \quad \Rightarrow \quad n = 6q \quad \Rightarrow \quad $ loại (chia hết cho 6)
$r = 1 \quad \Rightarrow \quad n = 6q + 1 \quad \Rightarrow \quad $ nhận
$r = 2 \quad \Rightarrow \quad n = 6q + 2 \quad \Rightarrow \quad n = 2(3q + 1) \quad \Rightarrow \quad $ loại (chia hết cho 2)
$r = 3 \quad \Rightarrow \quad n = 6q + 3 \quad \Rightarrow \quad n = 3(2q + 1) \quad \Rightarrow \quad $ loại (chia hết cho 3)
$r = 4 \quad \Rightarrow \quad n = 6q + 4 \quad \Rightarrow \quad n = 2(3q + 2) \quad \Rightarrow \quad $ loại (chia hết cho 2)
$r = 5 \quad \Rightarrow \quad n = 6q + 5 \quad \Rightarrow \quad $ nhận
\[\Rightarrow \left[ \begin{array}{ll} n = 6k + 1 \\[1mm] n = 6k + 5 \end{array} \right. \quad \Rightarrow \quad \left[ \begin{array}{ll} n = 6k + 1,\\[1mm] n = 6k - 1. \end{array} \right. \quad \forall n \ge 5\]$\Rightarrow$ Vì một trong 2 của biểu thức trên có thể là số nguyên tố mà dựa vào tính chất nếu $p \mid n$ thì $n$ không phải là số nguyên tố nên thay vì chạy $[2, \sqrt{n}]$ thì chỉ cần kiểm tra \(\quad \left[ \begin{array}{ll} p \mid n,\\[1mm] (p + 2) \mid n. \end{array} \right. \quad\) với $n \ge 5$ là đủ
Như vậy, ta tối ưu từ $O(\sqrt{n})$ xuống còn $O(\frac{\sqrt{n}}{6})$