순다람의 체를 사용하여 주어진 범위 사이의 소수를 생성하는 C++ 프로그램

이것은 주어진 범위 사이의 소수를 생성하기 위해 순다람의 체를 구현하는 C++ 프로그램입니다. 이 알고리즘은 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