พิมพ์จำนวนเฉพาะทั้งหมดน้อยกว่าหรือเท่ากับ N ใน C++

ในปัญหานี้ เราจะได้รับตัวเลข N และต้องพิมพ์จำนวนเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับ N

ตัวอย่างเพื่อความเข้าใจ

Input: 10
Output: 2 3 5 7

จำนวนเฉพาะ คือ จำนวนที่หารได้เฉพาะ 1 และตัวมันเอง เช่น 2, 3

วิธีง่ายคือวนลูปจาก 2 ถึง 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);
    return 0;
}

ผลลัพธ์

จำนวนเฉพาะที่น้อยกว่าหรือเท่ากับ 41 คือ

2 3 5 7 11 13 17 19 23 29 31 37 41