➗Kiểm tra số nguyên tố

Số nguyên tố là gì

Số nguyên tố là số nguyên lớn hơn hoặc bằng 2 và chỉ có hai ước số là 1 và chính nó. Những số như 2, 3, 5, 7, 11 là số nguyên tố, và 2 là số nguyên tố chẵn duy nhất.

1 có phải là số nguyên tố không

1 không phải là số nguyên tố. Số nguyên tố được định nghĩa là các số nguyên từ 2 trở lên, và nếu bao gồm 1 thì tính chất phân tích thành thừa số nguyên tố sẽ không còn đúng (mỗi số nguyên không thể được biểu diễn một cách duy nhất thành tích của các số nguyên tố).

Cách phân biệt số nguyên tố

Để xác định xem số nguyên n có phải là số nguyên tố hay không, hãy chia lần lượt cho các số nhỏ hơn hoặc bằng √n, nếu không có số nào chia hết thì n là số nguyên tố. Ví dụ, 91 chia hết cho 7 (nhỏ hơn √91 ≈ 9,5) nên 91 không phải là số nguyên tố.

• Phương pháp thử chia：Phương pháp thử chia là chia số n lần lượt cho các số từ 2 đến √n để tìm ước số, nhưng với các số có nhiều chữ số thì số lần chia sẽ rất lớn.
• Kiểm tra Miller-Rabin：Kiểm tra Miller-Rabin là phương pháp kiểm tra dư của lũy thừa với một số cơ số nhất định để tìm bằng chứng cho thấy số đó không phải là số nguyên tố, và có thể xác định các số lớn trong thời gian ngắn.