সুন্দরমের চালনি ব্যবহার করে একটি প্রদত্ত পরিসরের মধ্যে প্রাইম নম্বর তৈরি করতে C++ প্রোগ্রাম

দেওয়া রেঞ্জের মধ্যে প্রাইম নম্বর জেনারেট করতে সুন্দরমের সিভ বাস্তবায়নের জন্য এটি C++ প্রোগ্রাম। এই অ্যালগরিদমটি 1934 সালে সুন্দরম দ্বারা আবিষ্কৃত হয়েছিল।

অ্যালগরিদম

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