एराटोस्थनीज़ की छलनी ऊपरी सीमा n तक की सभी अभाज्य संख्याएँ सूचीबद्ध करती है, जिसमें n भी शामिल है। यहाँ Rust प्रोग्राम 1000 से अधिक नहीं होने वाली 168 अभाज्य संख्याएँ छापते हैं। सीमा शामिल है; 0 और 1 अभाज्य नहीं हैं।

छलनी के चरण और वर्ग से शुरू करने का कारण

1. 0 से n तक के सूचकांक इस्तेमाल करने के लिए n + 1 बूलियन तत्व आवंटित करें। मूल संस्करण उन्हें सत्य से प्रारंभ करता है और 0 तथा 1 को असत्य करता है। सीमा 2 से छोटी हो तो सूचकांक 1 तक पहुँचने से पहले खाली परिणाम लौटाता है।
2. 2 से शुरू करके संभावित मान p को बढ़ते क्रम में जाँचें। चिह्न अभी भी सत्य हो तो p अभाज्य है: \(p^2\) से शुरू करके p के अंतर से उसके गुणजों को असत्य चिह्नित करें। स्वयं p को न हटाएँ।
3. गुणज हटाने के लिए केवल \(p^2\le n\) पूरा करने वाले मानों तक जाना पर्याप्त है, क्योंकि हर भाज्य संख्या का कोई अभाज्य गुणनखंड उसके वर्गमूल से बड़ा नहीं होता।
4. अंत में 2 से n तक जाँचकर सत्य बचे सभी मान छापें। आउटपुट का दायरा वर्गमूल तक सीमित नहीं है।

\(p^2\) से छोटा गुणज \(kp\), जहाँ \(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)\) है। ये संक्रियाओं और भंडारण के अनंतस्पर्शी (asymptotic) अनुमान हैं, मापा गया समय या मनमानी परिशुद्धता के पूर्णांकों की बिट-जटिलता नहीं। Princeton की विश्लेषण सामग्री में छलनी का अभ्यास भी यही वृद्धि-दर बताता है।

Rust का bool एक बाइट लेता है और Vec<T> तत्वों को लगातार मेमोरी में रखता है। यह Vec<bool> बिट-पैक किया हुआ ऐरे नहीं है। चिह्नों के तार्किक तत्वों की संख्या n + 1 है; वेक्टर का मेटाडेटा, आवंटित क्षमता और लौटाए गए Vec<usize> के लिए भी स्थान चाहिए।

यदि n + 1 निरूपित नहीं किया जा सकता, तो checked_add से None मिलता है और उसके बाद का expect panic उत्पन्न करता है। अन्य मामलों में भी पर्याप्त मेमोरी उपलब्ध होनी चाहिए; मनमाने बड़े ऊपरी मान समर्थित नहीं हैं। बड़े अंतरालों के लिए खंडित छलनी पर विचार करें। किसी दायरे की अभाज्य संख्याएँ सूचीबद्ध करना, एक बड़े पूर्णांक की अभाज्यता जाँचने से अलग उपयोग है।