ในปัญหานี้ เราได้ตัวเลข N และต้องพิมพ์จำนวนเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับ N
มาดูตัวอย่างเพื่อทำความเข้าใจหัวข้อกันดีกว่า −
Input: 10 Output: 2 3 5 7
จำนวนเฉพาะ เป็นตัวเลขที่สามารถหารด้วยตัวเดียวเท่านั้นและตัวนับเอง ตัวอย่าง:2, 3
วิธีง่ายๆ คือการวนซ้ำจาก 2 ถึง N แล้วหารจำนวนด้วยมัน ถ้าจำนวนนั้นหารไม่ได้ แสดงว่าเป็นจำนวนเฉพาะ พิมพ์หมายเลข ทำจนจำนวนเท่ากับ N วิธีการนี้ไม่ได้ผล
วิธีที่มีประสิทธิภาพมากขึ้นคือการตรวจสอบจำนวนเฉพาะโดยการวนซ้ำจาก 2 ถึง √N
ตัวอย่าง
#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);
} ผลลัพธ์
จำนวนเฉพาะที่น้อยกว่าหรือเท่ากับ 41 คือ
2 3 5 7 11 13 17 19 23 29 31 37 41
