โปรแกรม C++ การถาลเอราโทสเตนีส (Sieve of Eratosthenes) สร้างจำนวนเฉพาะ

การถาลเอราโทสเตนีส (Sieve of Eratosthenes)

นี่คือโปรแกรม C++ สำหรับการนำการถาลเอราโทสเตนีสมาใช้สร้างจำนวนเฉพาะในช่วงที่กำหนด ในวิธีนี้ ใช้อาร์เรย์จำนวนเต็มที่เริ่มต้นทุกองค์ประกอบเป็นศูนย์

วิธีนี้ทำงานโดยทำเครื่องหมายดัชนีขององค์ประกอบที่ไม่ใช่จำนวนเฉพาะเป็น 1 ภายในลูปซ้อน (nested loops) จำนวนเฉพาะคือตัวเลขที่ดัชนีของมันถูกทำเครื่องหมายเป็น 0

อัลกอริทึม

เริ่มต้น
  ประกาศอาร์เรย์ขนาด n และเริ่มต้นเป็นศูนย์
  ประกาศ length, i, j
  อ่าน length
  For i = 2 ถึง n-1
    For j = i*i ถึง n-1
      Arr[j-1] = 1
  For i = 1 ถึง n
    If(arr[i-1] == 0)
      พิมพ์ i
สิ้นสุด

โค้ดตัวอย่าง

#include <iostream>
const int len = 30;

int main() {
    int arr[30] = {0};
    for (int i = 2; i < 30; i++) {
        for (int j = i * i; j < 30; j += i) {
            arr[j - 1] = 1;
        }
    }
    for (int i = 1; i < 30; i++) {
        if (arr[i - 1] == 0)
            std::cout << i << "\t";
    }
}

ผลลัพธ์ตัวอย่าง

1 2 3 5 7 11 13 17 19 23 29