Số nguyên tố là số chỉ chia hết cho hai số chính nó và một số. Thừa số của một số là một số có thể chia nó.
Danh sách mười số nguyên tố đầu tiên là 2,3,5,7,11,13,17,23,29,31.
Một số không phải là số nguyên tố là một số hợp. Một số tổng hợp là một số có thể chia cho nhiều hơn hai số.
Sau đó Elser là số nguyên tố và hợp số có 1 không phải là số nguyên tố cũng không phải là hợp số vì nó chỉ có thể chia cho chính nó.
Cách kiểm tra xem một số là số nguyên tố hay hợp số để kiểm tra xem một số là số nguyên tố, có hai điều kiện cần được kiểm tra
1) Nó phải là một số nguyên lớn hơn 1.
2) nó chỉ nên có hai yếu tố, tức là một và chính con số.
Nếu hai điều kiện này được thỏa mãn, thì chúng ta có thể nói một số là số nguyên tố.
Trong chương trình của chúng tôi, chúng tôi sẽ kiểm tra việc chia số cho mỗi số nhỏ hơn số đó. Nếu bất kỳ số nào nhỏ hơn số đã cho chia nó thì nó không phải là số Nguyên tố. Nếu không, nó là một số nguyên tố.
Hãy lấy một ví dụ về hai số và kiểm tra xem chúng có phải là số nguyên tố hay không bằng quy trình này.
Input − Number1 − 42 Output − 42 is not a prime number
Logic - Chúng ta sẽ chia 42 cho mọi số lớn hơn 1 và nhỏ hơn 42. Vì vậy,
42/2 =21 tức là 42 chia hết cho 2, điều này có nghĩa là 42 không phải là số nguyên tố vì nó chia hết cho một số khác.
Input − Number2 − 7 Output − 7 is a prime number
Logic - Chúng ta sẽ chia bảy cho mọi số lớn hơn 1 và nhỏ hơn 7. Vì vậy,
7 không chia hết cho 2, vì vậy mã sẽ kiểm tra số tiếp theo, tức là 3
7 không chia hết cho 3, vì vậy mã sẽ kiểm tra số tiếp theo, tức là 4
7 không chia hết cho 4, vì vậy mã sẽ kiểm tra số tiếp theo, tức là 5
7 không chia hết cho 5, vì vậy mã sẽ kiểm tra số tiếp theo, tức là 6
7 không chia hết cho 6, điều này có nghĩa là 7 chỉ chia hết cho 1 và 7 điều này có nghĩa là 7 là một số nguyên tố.
hãy nhìn vào logic ở trên, con số sẽ là 1000 Plus hay 100000 Plus thì chương trình sẽ lấy nhiều lần lặp lại cho vòng lặp for một phương pháp này sẽ mất rất nhiều thời gian tính toán. Vì vậy, để giảm số lần lặp lại, chúng phải là một cách tốt hơn.
Một giải pháp tối ưu cho điều này là chỉ chạy nửa vòng. điều này có nghĩa là nếu con số là 77, vòng lặp sẽ chỉ chạy cho đến 38. Điều này sẽ làm giảm số lần lặp lại cần thiết, vì vậy chúng tôi sẽ sử dụng thuật toán này để tạo chương trình của mình.
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);
}
} Đầu ra
33 is a prime number