นี่คือโปรแกรม C ++ ที่ใช้ Sieve of Sundaram เพื่อสร้าง Prime Numbers ระหว่างช่วงที่กำหนด อัลกอริทึมนี้ถูกค้นพบในปี 1934 โดย Sundaram
อัลกอริทึม
Begin
printPrimes(n)
Here we find out primes
smaller than n, we reduce n-2 to half. We call it New.
New = (n-2)/2;
Create an array marked[n] that is going
to be used to separate numbers of the form i+j+2ij from
others where 1 <= i <= j
Initialize all entries of marked[] as false.
Mark all numbers of the form i + j + 2ij as true
where 1 <= i <= j
for i=1 to New
a) j = i;
b) Loop While (i + j + 2*i*j) 2, then print 2 as first prime.
Remaining primes are of the form 2i + 1 where i is
index of NOT marked numbers. So print 2i + 1 for all i
such that marked[i] is false.
End โค้ดตัวอย่าง
#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
