يسرد غربال إراتوستينس جميع الأعداد الأولية حتى الحد الأعلى n شاملًا هذا الحد. تطبع برامج Rust هنا الأعداد الأولية الـ168 التي لا تتجاوز 1000. الحد مشمول؛ و0 و1 ليسا عددين أوليين.

خطوات الغربال وسبب البدء بالمربع

1. خصّص n + 1 عنصرًا منطقيًا لاستخدام الفهارس من 0 إلى n. تهيئ النسخة الأساسية العناصر إلى صحيح، ثم تجعل 0 و1 خطأ. إذا كان الحد أقل من 2، تعيد نتيجة فارغة قبل الوصول إلى الفهرس 1.
2. افحص المرشحين p بترتيب تصاعدي بدءًا من 2. إذا بقيت العلامة صحيحة، فإن p أولي: اجعل علامات مضاعفاته خطأ بدءًا من \(p^2\) وبخطوة مقدارها p. لا تشطب p نفسه.
3. يكفي شطب المضاعفات للمرشحين الذين يحققون \(p^2\le n\)، لأن لكل عدد مؤلف عاملًا أوليًا لا يتجاوز جذره التربيعي.
4. في النهاية، افحص الأعداد من 2 إلى n واطبع كل عدد بقيت علامته صحيحة. نطاق الإخراج لا يقتصر على الجذر التربيعي.

المضاعف \(kp\) الأصغر من \(p^2\)، حيث \(2\le k<p\)، سبق شطبه بواسطة عامل أولي للعدد k أصغر من p. هذا لا يعني أن سرد جميع الأعداد الأصغر قد اكتمل.

الصورة: SKopp، نسخة حدّثها Suricata، Wikimedia Commons، CC BY-SA 3.0. لم يُعدّل الملف. يوضح الرسم الأعداد من 2 إلى 120، بينما تستخدم البرامج أدناه الحد 1000.

التنفيذ الأساسي في Rust

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

fn sieve(n: usize) -> Vec<usize> {
    if n < 2 {
        return Vec::new();
    }
    let len = n.checked_add(1).expect("n + 1 is too large");
    let mut is_prime = vec![true; len];
    is_prime[0] = false;
    is_prime[1] = false;

    let mut p = 2;
    while p <= n / p {
        if is_prime[p] {
            let mut multiple = p * p;
            loop {
                is_prime[multiple] = false;
                if n - multiple < p {
                    break;
                }
                multiple += p;
            }
        }
        p += 1;
    }

    (2..=n).filter(|&i| is_prime[i]).collect()
}

fn main() {
    for prime in sieve(1000) {
        println!("{}", prime);
    }
}

احفظ باسم sieve.rs وترجم باستخدام rustc --edition=2021 sieve.rs -o sieve. في Windows، اجعل اسم الملف التنفيذي sieve.exe. يطبع التشغيل 168 سطرًا، أول عدد فيها 2 وآخرها 997. شُغّلت هذه الأمثلة باستخدام Rust 1.90.0.

تعيد sieve(0) وsieve(1) متجهًا فارغًا، بينما تعيد sieve(2) القيمة [2]. يضمن الشرط p <= n / p حساب p * p فقط عندما لا يتجاوز المربع الحد. وتُفحص المسافة المتبقية قبل إضافة المضاعف التالي. لا حاجة إلى جذر تربيعي باستخدام الفاصلة العائمة.

نسخة تشطب المرشحين الفرديين فقط

الأعداد الزوجية الأكبر من 2 مؤلفة. لذا يمكن جعل علامة 2 صحيحة وتهيئة الأعداد الفردية فقط كمرشحين. مربع العدد الأولي الفردي p فردي أيضًا؛ والانطلاق منه بخطوة \(2p\) يزور المضاعفات الفردية فقط.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

fn sieve_odd(n: usize) -> Vec<usize> {
    if n < 2 {
        return Vec::new();
    }
    let len = n.checked_add(1).expect("n + 1 is too large");
    let mut is_prime = vec![false; len];
    is_prime[2] = true;
    for i in (3..=n).step_by(2) {
        is_prime[i] = true;
    }

    let mut p = 3;
    while p <= n / p {
        if is_prime[p] {
            let step = 2 * p;
            let mut multiple = p * p;
            loop {
                is_prime[multiple] = false;
                if n - multiple < step {
                    break;
                }
                multiple += step;
            }
        }
        p += 2;
    }

    (2..=n).filter(|&i| is_prime[i]).collect()
}

fn main() {
    for prime in sieve_odd(1000) {
        println!("{}", prime);
    }
}

احفظ هذه النسخة في ملف آخر وترجمها. تطبع الأعداد الأولية الـ168 نفسها، وتعيد نتيجة فارغة للحدين 0 و1، و[2] للحد 2. لا تجمع دالتي main في ملف واحد.

تتجنب هذه النسخة بعض العمل على الأعداد الزوجية. لكن التهيئة إلى خطأ لا تضمن سرعة أعلى دائمًا. يعتمد الزمن على التهيئة والكتابة والوصول إلى الذاكرة والمترجم والآلة. لا توجد هنا مقارنة لأزمنة مقاسة. تظل المصفوفة مؤلفة من n + 1 عنصرًا كي تقابل الفهارس الأعداد مباشرة.

التعقيد والحدود الممكنة

في نموذج RAM المعتاد، يحتاج الغربال إلى زمن \(O(n\log\log n)\) ومساحة \(O(n)\) للعلامات. هذه تقديرات تقاربية للعمليات والتخزين، وليست أزمنة مقاسة أو تعقيدًا على مستوى البتات لأعداد صحيحة ذات دقة اعتباطية. ويعرض تمرين الغربال في مادة التحليل من Princeton معدل النمو نفسه.

يشغل bool في Rust بايتًا واحدًا، ويخزن Vec<T> العناصر بصورة متجاورة. هذا Vec<bool> ليس مصفوفة بتات مضغوطة. العدد المنطقي للعلامات هو n + 1؛ كما تتطلب بيانات إدارة المتجه والسعة المخصصة والمتجه المعاد Vec<usize> مساحة إضافية.

إذا تعذر تمثيل n + 1، تعيد checked_add القيمة None، ثم يستدعي expect حالة panic. وفي الحالات الأخرى، لا بد من توفر ذاكرة كافية؛ فلا يدعم التنفيذ حدودًا كبيرة كيفما اتفق. للفترات الكبيرة، يمكن النظر في الغربال المجزأ. سرد الأعداد الأولية في نطاق يختلف في غرضه عن اختبار عدد صحيح كبير واحد.