Trong bài toán này, chúng ta được cho một số N và chúng ta phải in ra tất cả các số nguyên tố nhỏ hơn hoặc bằng N.
Hãy lấy một ví dụ để hiểu rõ hơn về chủ đề -
Input: 10 Output: 2 3 5 7
Một số nguyên tố là số chỉ có thể chia cho một và chính số đó. Ví dụ:2, 3.
Một cách tiếp cận đơn giản là lặp lại từ 2 đến N và chia số cho nó. Nếu số không chia hết thì đó là số nguyên tố. In số. Làm điều này cho đến khi con số bằng N. Cách tiếp cận này không hiệu quả.
Một cách tiếp cận hiệu quả hơn sẽ là kiểm tra số nguyên tố bằng cách lặp lại từ 2 đến √N.
Ví dụ
#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<<"Prime numbers less than or equal to "<<n<<" are \n";
printPrime(n);
} Đầu ra
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