Số nguyên tố chỉ chia hết cho 1 và chính nó. 10 số nguyên tố đầu: 2,3,5,7,11,13,17,23,29,31. Số không phải nguyên tố gọi là hợp số (chia hết cho >2 số). 1 không phải nguyên tố cũng không phải hợp số.
Kiểm tra số nguyên tố: (1) số nguyên > 1; (2) chỉ có 2 ước là 1 và chính nó. Chương trình chia cho mọi số nhỏ hơn nó. Nếu chia hết cho số nào thì không phải nguyên tố. Tối ưu: chỉ lặp đến n/2.
Input: 42 Output: 42 is not a prime number Logic: 42 chia hết cho 2 => không phải nguyên tố. Input: 7 Output: 7 is a prime number Logic: 7 không chia hết cho 2,3,4,5,6 => là nguyên tố.
Nếu số lớn (1000+), lặp đến n/2 giảm số lần lặp đáng kể.
Ví dụ
#include <stdio.h>
int main() {
int num = 33, flag = 0;
for(int i=2 ; i < num/2 ; i++) {
if(num%i == 0) {
printf("%d is not a prime number", num);
flag = 1;
break;
}
}
if(flag == 0) {
printf("%d is a prime number", num);
}
}
Kết quả
33 is a prime number