Trong bài toán này, cho một số N, ta phải in ra tất cả các số nguyên tố nhỏ hơn hoặc bằng N.
Ví dụ:
Input: 10 Output: 2 3 5 7
Số nguyên tố là số chỉ chia hết cho 1 và chính nó. Ví dụ: 2, 3.
Cách đơn giản là duyệt từ 2 đến N và kiểm tra tính nguyên tố. Cách này không hiệu quả.
Cách tốt hơn: kiểm tra nguyên tố bằng cách duyệt từ 2 đến √N.
Chương trình minh họa
#include <bits/stdc++.h>
using namespace std;
bool isPrimeNumber(int n){
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
void printPrime(int n){
for (int i = 2; i <= n; i++) {
if (isPrimeNumber(i))
cout << i << " ";
}
}
int main(){
int n = 41;
cout << "Các số nguyên tố nhỏ hơn hoặc bằng " << n << " là \n";
printPrime(n);
return 0;
}
Kết quả
Các số nguyên tố nhỏ hơn hoặc bằng 41 là:
2 3 5 7 11 13 17 19 23 29 31 37 41