Xay dung thuat toan cho Nla so nguyen to khi N khong co uoc nao trong pham vi tu 2 den canN

Lời giải chi tiết

Ý tưởng: Số nguyên tố là số nguyên lớn hơn $1$ chỉ có hai ước dương là $1$ và chính nó. Nếu $N$ có ước khác $1$ và $N$, thì $N$ có ít nhất một ước không vượt quá $\sqrt N$. Vì vậy, chỉ cần thử các ước trong phạm vi này.

Thuật toán:

1. Nhập số nguyên $N$.
2. Nếu $N\le 1$, thông báo “$N$ không là số nguyên tố” và kết thúc.
3. Đặt $i=2$. Khi $i^2\le N$, thực hiện: nếu $N$ chia hết cho $i$, thông báo “$N$ không là số nguyên tố” và kết thúc; nếu không, tăng $i$ thêm $1$.
4. Nếu đã thử hết mà không tìm thấy ước, thông báo “$N$ là số nguyên tố”.

Điều kiện $i^2\le N$ tương đương với $i\le\sqrt N$ khi $N>1$, nên thuật toán đã xét đúng phạm vi các ước cần kiểm tra.

Kiến thức cần nhớ

• Số nguyên tố là số nguyên lớn hơn $1$ chỉ có hai ước dương là $1$ và chính nó.
• Muốn kiểm tra $N>1$ có ước khác $1$ và $N$ hay không, chỉ cần thử các số nguyên từ $2$ đến $\sqrt N$.

Lỗi thường gặp

• Quên xét riêng trường hợp $N\le 1$.
• Dừng vòng lặp khi $i^2=N$, làm bỏ sót ước $\sqrt N$ của số chính phương.