Số nguyên tố là số nguyên lớn hơn một và các thừa số duy nhất của số nguyên tố phải là một và chính nó. Một số số nguyên tố đầu tiên là -
2, 3, 5, 7, 11, 13 ,17
Chương trình kiểm tra xem một số có phải là số nguyên tố hay không như sau.
Ví dụ
#include <iostream>
using namespace std;
int main() {
int n=17, i, flag = 0;
for(i=2; i<=n/2; ++i) {
if(n%i==0) {
flag=1;
break;
}
}
if (flag==0)
cout<<n<<" is a prime number";
else
cout<<n<<" is not a prime number";
return 0;
} Đầu ra
17 is a prime number
Trong chương trình trên, có một vòng lặp chạy từ 2 đến nửa số n, với n là số cần xác định. Mỗi giá trị của vòng lặp chia n. Nếu phần dư của phép chia này là 0, điều đó có nghĩa là n chia hết cho một số, không phải một hay chính nó. Vì vậy, nó không phải là một số nguyên tố và cờ được đặt thành 1. Sau đó, câu lệnh break được sử dụng để thoát khỏi vòng lặp.
for(i=2; i<=n/2; ++i) {
if(n%i==0) {
flag=1;
break;
}
} Nếu giá trị của cờ vẫn bằng 0, thì số đó là số nguyên tố và được hiển thị. Nếu giá trị của cờ được thay đổi thành một, thì số đó không phải là số nguyên tố và số đó sẽ được hiển thị.
if (flag==0) cout<<n<<" is a prime number"; else cout<<n<<" is not a prime number";