يحتفظ مثال Rust هذا بالأعداد الأولية المكتشفة ويستخدمها في القسمة التجريبية. تعيد primes_up_to(max) قائمة الأعداد الأولية حتى الحد الأعلى شاملًا. يوجد 168 عددًا أوليًا لا يتجاوز 1000؛ والعددان 0 و1 ليسا أوليين. هذا ليس تطبيقًا للغربال.

الشيفرة

 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

fn primes_up_to(max: usize) -> Vec<usize> {
    if max < 2 {
        return Vec::new();
    }
    let mut primes = vec![2];
    let mut n = 3;
    while n <= max {
        let mut is_prime = true;
        for &p in &primes {
            if p > n / p {
                break;
            }
            if n % p == 0 {
                is_prime = false;
                break;
            }
        }
        if is_prime {
            primes.push(n);
        }
        if max - n < 2 {
            break;
        }
        n += 2;
    }
    primes
}

fn main() {
    for p in primes_up_to(1000) {
        println!("{}", p);
    }
}

التشغيل والحدود الصغيرة

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

تعيد primes_up_to(0) وprimes_up_to(1) متجهًا فارغًا؛ وتعيد primes_up_to(2) القيمة [2]، وprimes_up_to(3) القيمة [2, 3]، وprimes_up_to(10) القيمة [2, 3, 5, 7]. نوع المعامل usize لا يشمل الحدود السالبة. لا يحلل هذا البرنامج بيانات الإدخال القياسي.

آلية الاختبار والحلقة

1. أعد نتيجة فارغة إذا كان الحد أقل من 2. وإلا فاحتفظ بالعدد 2، واختبر المرشحين الفرديين فقط من 3 حتى الحد. يُفحص الحد قبل معالجة المرشح، لذلك لا يُضاف 3 عندما يكون الحد 2.
2. للمرشح المركب n عامل أولي لا يتجاوز جذره التربيعي. هذه الأعداد الأولية موجودة بالفعل في القائمة بفضل المرشحين السابقين. إذا كان باقي قسمة ما صفرًا، فارفض المرشح. وإذا لم يُعثر على قاسم عند تحقق p > n / p، فلا حاجة إلى متابعة القسمة التجريبية. تعبّر قسمة الأعداد الصحيحة الموجبة عن شرط الجذر التربيعي دون حساب p * p أو جذر بأعداد الفاصلة العائمة.
3. تستعير for &p in &primes القائمة، وتتلقى مراجع بالتتابع، وتنسخ كل قيمة من نوع usize إلى p. لا يُضاف عدد أولي جديد إلا بعد انتهاء هذه الحلقة. أما for p in primes_up_to(1000) الأخيرة فتأخذ القيم من المتجه المُعاد وتطبعها. تميز وثائق Vec في Rust بين التكرار بالاستعارة والتكرار الذي يتولى ملكية المتجه ويستهلكه.
4. داخل الشرط n <= max لا يمكن أن تكون max - n سالبة. إذا كانت المسافة المتبقية أقل من 2، فتوقف قبل الجمع؛ وإلا نفّذ n += 2. وهكذا لا تتجاوز الزيادة الحد.

نطاق الاستخدام

يطبع البرنامج الأصلي ذو الحد الثابت 1000 أيضًا 168 عددًا أوليًا على نحو صحيح. لكن تغيير الحد وحده إلى 0 أو 1 أو 2 يطبع قيمًا مثل 2 أو 3 خارج النطاق، لأن الحد لا يُفحص قبل المعالجة. تعالج الدالة القابلة لإعادة الاستخدام هنا هذه الحالات الحدية.

تخزن القائمة قيمة usize لكل عدد أولي مكتشف. وتحتاج بيانات المتجه الوصفية والسعة المخصصة إلى ذاكرة أيضًا. حد أعلى تقريبي لعدد عمليات القسمة هو O(max sqrt(max)) عند عدّ كل قسمة عملية واحدة؛ وهذا ليس زمنًا مقاسًا ولا تعقيدًا على مستوى البتات. تتطلب الحدود الأكبر وقتًا وتخزينًا أكثر، دون ضمان سرد سريع للأعداد الأولية حتى حدود كبيرة كيفما كانت. للفترات الكبيرة راجع مقال غربال إراتوستينس. هذا ليس مولّدًا للأعداد الأولية المستخدمة في التشفير.