โปรแกรม C++ สร้างจำนวนเฉพาะในช่วงที่กำหนดด้วยการถาลซุนดาราม (Sieve of Sundaram)

การถาลซุนดาราม (Sieve of Sundaram)

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

อัลกอริทึม

เริ่มต้น printPrimes(n)
  หาจำนวนเฉพาะที่น้อยกว่า n โดยลด n-2 ลงครึ่งหนึ่ง เรียกว่า New
  New = (n-2)/2
  สร้างอาร์เรย์ marked[n] เพื่อแยกตัวเลขรูปแบบ i+j+2ij จากตัวเลขอื่น โดยที่ 1 <= i <= j
  เริ่มต้นทุกค่าใน marked[] เป็น false
  ทำเครื่องหมายตัวเลขรูปแบบ i + j + 2ij เป็น true โดยที่ 1 <= i <= j
  for i=1 ถึง New
    a) j = i
    b) วนลูป While (i + j + 2*i*j) <= New
       marked[i + j + 2*i*j] = true
  หาก n > 2 ให้พิมพ์ 2 เป็นจำนวนเฉพาะตัวแรก
  จำนวนเฉพาะที่เหลือจะอยู่ในรูปแบบ 2i + 1 โดยที่ i คือดัชนีของตัวเลขที่ไม่ถูกทำเครื่องหมาย
  พิมพ์ 2i + 1 สำหรับทุก i ที่ marked[i] เป็น false
สิ้นสุด

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

#include <bits/stdc++.h>
using namespace std;

int SieveOfSundaram(int m) {
    int N = (m-2)/2;
    bool marked[N + 1];
    memset(marked, false, sizeof(marked));
    for (int i=1; i<=N; i++)
        for (int j=i; (i + j + 2*i*j) <= N; j++)
            marked[i + j + 2*i*j] = true;
    
    if (m > 2)
        cout << 2 << " ";
    
    for (int i=1; i<=N; i++)
        if (marked[i] == false)
            cout << 2*i + 1 << " ";
}

int main(void) {
    int m = 10;
    SieveOfSundaram(m);
    return 0;
}

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

2 3 5 7