C++ প্রোগ্রাম: সুন্দরামের ছাঁনি ব্যবহার করে নির্দিষ্ট পরিসরের মৌলিক সংখ্যা তৈরি

এটি সুন্দরামের ছাঁনি (Sieve of Sundaram) বাস্তবায়ন করে দত্তক পরিসরের মৌলিক সংখ্যা তৈরি করার C++ প্রোগ্রাম। এই অ্যালগরিদম ১৯৩৪ সালে সুন্দরাম আবিষ্কার করেছিলেন।

অ্যালগরিদম

শুরু 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 to New
    a) j = i;
    b) লুপ চলাকালীন (i + j + 2*i*j) <= N
        marked[i + j + 2*i*j] = true
যদি m > 2 হয়, তবে ২ প্রথম মৌলিক সংখ্যা হিসেবে প্রিন্ট করুন।
বাকি মৌলিক সংখ্যাগুলো 2i + 1 রূপের যেখানে i হলো NOT marked সংখ্যাগুলোর ইনডেক্স।
সুতরাং marked[i] false হলে 2i + 1 প্রিন্ট করুন।
শেষ

উদাহরণ কোড

#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