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

এটি অ্যাটকিনের ছাঁনি (Sieve of Atkin) বাস্তবায়ন করে দত্তক পরিসরের মৌলিক সংখ্যা তৈরি করার C++ প্রোগ্রাম। অ্যাটকিনের ছাঁনি একটি আধুনিক অ্যালগরিদম যা নির্দিষ্ট পূর্ণসংখ্যা পর্যন্ত সকল মৌলিক সংখ্যা খুঁজে বের করার জন্য ব্যবহৃত হয়।

অ্যালগরিদম

শুরু
    ফলাফল তালিকা তৈরি করুন, ২, ৩, এবং ৫ দিয়ে ভর্তি করুন
    ছাঁনি অ্যারে false ভ্যালু দিয়ে ইনিশিয়ালাইজ করুন
    siev[n] true হবে যদি নিচের যেকোনো একটি সত্য হয়:
    a) n = (4*x*x) + (y*y) विषম সংখ্যক সমাধান থাকে
       n % 12 = 1 বা n % 12 = 5
    b) n = (3*x*x) + (y*y) বিষম সংখ্যক সমাধান থাকে এবং n % 12 = 7
    c) n = (3*x*x) - (y*y) বিষম সংখ্যক সমাধান থাকে, x > y এবং n % 12 = 11
    বর্গের গুণফলগুলোকে নন-প্রাইম হিসেবে চিহ্নিত করুন
    sieve[] ব্যবহার করে মৌলিক সংখ্যা প্রিন্ট করুন
শেষ

উদাহরণ কোড

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

int SieveOfAtkin(int lmt) {
    if (lmt > 2)
        cout << 2 << " ";
    if (lmt > 3)
        cout << 3 << " ";
    bool sieve[lmt];
    for (int i = 0; i < lmt; i++)
        sieve[i] = false;
    for (int a = 1; a * a < lmt; a++) {
        for (int b = 1; b * b < lmt; b++) {
            // অ্যাটকিনের ছাঁনির মূল অংশ
            int n = (4 * a * a) + (b * b);
            if (n <= lmt && (n % 12 == 1 || n % 12 == 5))
                sieve[n] ^= true;
            n = (3 * a * a) + (b * b);
            if (n <= lmt && n % 12 == 7)
                sieve[n] ^= true;
            n = (3 * a * a) - (b * b);
            if (a > b && n <= lmt && n % 12 == 11)
                sieve[n] ^= true;
        }
    }
    for (int r = 5; r * r < lmt; r++) {
        if (sieve[r]) {
            for (int i = r * r; i < lmt; i += r * r)
                sieve[i] = false;
        }
    }
    for (int x = 5; x < lmt; x++)
        if (sieve[x])
            cout << x << " ";
}

int main(void) {
    int lmt = 30;
    SieveOfAtkin(lmt);
    return 0;
}

আউটপুট

2 3 5 7 11 13 17 19 23 29