Biết định nghĩa đầu tiên
Số nguyên tố là số nguyên lớn hơn 1 với đúng hai ước số dương: 1 và chính số đó. Các số nguyên tố đầu tiên là 2, 3, 5, 7, 11 và 13. Số 1 không phải là số nguyên tố cũng không phải hợp số và 2 là số nguyên tố chẵn duy nhất.
Chỉ kiểm tra đến căn bậc hai
Để kiểm tra số nguyên dương n, bạn không cần thử mọi số bên dưới n. Nếu n có hệ số lớn hơn căn bậc hai của nó thì nó cũng phải có hệ số phù hợp nhỏ hơn căn bậc hai. Vì vậy, việc kiểm tra các ước số có thể có đến căn bậc hai là đủ.
- Nếu số đó nhỏ hơn 2 thì không phải là số nguyên tố.
- Kiểm tra xem nó có chia hết cho 2 hay không. Nếu nó chẵn và lớn hơn 2 thì đó không phải là số nguyên tố.
- Hãy thử các ước số lẻ từ 3 đến căn bậc hai. Nếu có chia đều thì số đó là hợp số.
- Nếu không có số nào chia đều thì số đó là số nguyên tố.
Ví dụ: 97 có phải là số nguyên tố không?
Căn bậc hai của 97 nhỏ hơn 10 một chút. Kiểm tra các ước nguyên tố có thể có cho đến thời điểm đó: 2, 3, 5 và 7. Số này không chia hết cho bất kỳ số nào trong số đó nên 97 là số nguyên tố.
Với 91, kiểm tra tìm thấy 7: 91 ÷ 7 = 13. Điều đó đủ để chứng tỏ rằng 91 là hợp số; không cần phải kiểm tra các ước số lớn hơn.
Những lỗi thường gặp
- Gọi 1 số nguyên tố. Một số nguyên tố phải có chính xác hai ước số dương, còn số 1 chỉ có một ước số dương.
- Giả sử mọi số lẻ đều là số nguyên tố. Các số lẻ như 9, 15, 21 và 91 có ước số lẻ.
- Chỉ kiểm tra một vài ước số nhỏ cho một số lớn. Việc kiểm tra phải bao gồm mọi ước số có thể có cho đến căn bậc hai hoặc sử dụng thuật toán nguyên tố đã được xác minh.
UsefulVerse kiểm tra dữ liệu đầu vào số nguyên thực tế cục bộ trong trình duyệt của bạn. Kết quả chính là kiểm tra tính chia hết, không phải là bằng chứng về khóa mật mã hay sự thay thế cho phần mềm lý thuyết số chuyên dụng.