غربال إراتوستينس

نعلم كيفية التحقق مما إذا كان عدد واحد أولياً (\(O(\sqrt{N})\)). ولكن ماذا لو كنت بحاجة لإيجاد جميع الأعداد الأولية حتى \(1,000,000\)؟

استخدام الطريقة السابقة داخل حلقة سيكون بطيئاً جداً (\(N \times \sqrt{N}\)). نحتاج إلى عملية مجمعة. نحتاج إلى غربال.

المفهوم

بدلاً من فحص الأعداد واحداً تلو الآخر، نقوم بتصفيتها.

تخيل كتابة جميع الأعداد من 1 إلى 20. 1. نعلم أن 2 أولي. ضع دائرة حوله. الآن اشطب جميع مضاعفات 2 (4، 6، 8، 10…). 2. العدد التالي غير المشطوب هو 3. ضع دائرة حوله. اشطب جميع مضاعفات 3 (6، 9، 12…). 3. العدد التالي غير المشطوب هو 5 (4 مشطوب). ضع دائرة حوله. اشطب المضاعفات…

بحلول الوقت الذي تصل فيه إلى النهاية، تبقى الأعداد الأولية فقط غير مشطوبة.

الخوارزمية

نستخدم مصفوفة منطقية isPrime[] حيث isPrime[i] صحيح إذا كان i محتمل أن يكون أولياً. في البداية، نفترض أن كل شيء أولي.

الخطوات الأساسية:

1. أنشئ مصفوفة من القيم المنطقية، اجعلها جميعاً true.
2. ضع علامة على 0 و 1 كـ false (ليسا أوليين).
3. ابدأ الحلقة من i = 2.
4. إذا كان i أولياً (true)، فهذا يعني أنه لا يوجد عدد أصغر قسمه.
5. حلقة عبر جميع مضاعفات i (2*i، 3*i…) وضع عليها علامة false.

الكود

#include <iostream>
#include <vector>
using namespace std;

// Maximum number we want to check (e.g., 1 million)
const int MAX_N = 1000000;
vector<bool> is_prime(MAX_N + 1, true); // Assume all are prime first

void sieve() {
    is_prime[0] = is_prime[1] = false; // Edge cases

    for (int i = 2; i * i <= MAX_N; i++) {
        // If i is not crossed out yet, it is a prime
        if (is_prime[i]) {
            // Cross out all multiples of i
            // Optimization: Start from i * i (smaller multiples are already handled)
            for (int j = i * i; j <= MAX_N; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

لماذا نبدأ من \(i \times i\)؟

هذا تحسين حاسم. عندما \(i = 5\)، لماذا لا نشطب 10 (\(2 \times 5\)) أو 15 (\(3 \times 5\))؟

• لأن 10 تم شطبه بالفعل بواسطة 2.
• لأن 15 تم شطبه بالفعل بواسطة 3.

أول مضاعف لـ 5 لم يُلمس بعد هو \(5 \times 5 = 25\).

التعقيد

هذه الخوارزمية فعالة بشكل مشهور. على الرغم من وجود حلقات متداخلة، فهي بشكل مفاجئ ليست \(O(N^2)\). إنها \(O(N \log (\log N))\). هذا تقريباً خطي. بالنسبة لـ \(N = 10^7\) (10 مليون)، تعمل في جزء من الثانية.

مثال على مسألة

Noldbach

Noldbach

ينص Noldbach على أن على الأقل \(k\) عدداً أولياً من \(2\) إلى \(n\) شاملاً يمكن التعبير عنه كمجموع ثلاثة أعداد صحيحة: عددان أوليان متجاوران و \(1\). على سبيل المثال، \(19 = 7 + 11 + 1\)، أو \(13 = 5 + 7 + 1\).

يُطلق على عددين أوليين اسم متجاورين إذا لم تكن هناك أعداد أولية أخرى بينهما.

اكتشف ما إذا كان Noldbach على حق أم على خطأ.

Solution

لحل هذا، نحتاج إلى قائمة بجميع الأعداد الأولية بين \(2\) و \(n\). بينما يمكنك اختبار كل عدد بشكل فردي، فإن غربال إراتوستينس أسرع لتوليد قائمة من الأعداد الأولية في نطاق.

بعد سرد جميع الأعداد الأولية حتى \(n\)، يجب أن نتحقق من كل عددين أوليين متتاليين \(p\) و \(q\)، ما إذا كان \(p + q + 1\) عدداً أولياً (تذكر من الدرس الأخير كيفية القيام بذلك!).

#include <iostream>
#include <vector>
using namespace std;

// Maximum number we want to check (e.g., 1 million)
const int MAX_N = 1000000;
vector<bool> is_prime(MAX_N + 1, true); // Assume all are prime first
vector<int> primes;

int findPrime(int n) {
    is_prime[0] = is_prime[1] = false; // Edge cases

    for (int i = 2; i * i <= MAX_N; i++) {
        // If i is not crossed out yet, it is a prime
        if (is_prime[i]) {
            // Cross out all multiples of i
            // Optimization: Start from i * i (smaller multiples are already handled)
            for (int j = i * i; j <= MAX_N; j += i) {
                is_prime[j] = false;
            }
        }
    }

    for (int i = 2; i <= n; ++i){
        if (is_prime[i]) // We only care about prime numbers
            primes.push_back(i);
    }

    int count = 0;
    for (int i = 1; i < (int)primes.size(); ++i){
        if (is_prime[primes[i] + primes[i-1] + 1]){ // check whether consecutive primes + 1 is a prime
            count++;
        }
    }

    return count;
}


int main() { 
    int n, k;
    cin >> n >> k;

    int count = findPrime(n);

    if (count >= k)
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}