यह Rust उदाहरण अब तक मिली अभाज्य संख्याओं को सहेजकर परीक्षण विभाजन में इस्तेमाल करता है। primes_up_to(max) सीमा सहित उस सीमा तक की अभाज्य संख्याओं की सूची लौटाता है। 1000 से छोटी या बराबर 168 अभाज्य संख्याएँ हैं; 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 से सीमा तक केवल विषम उम्मीदवार जाँचें। उम्मीदवार को संसाधित करने से पहले सीमा जाँची जाती है, इसलिए सीमा 2 होने पर 3 नहीं जुड़ता।
2. भाज्य उम्मीदवार n का कम से कम एक अभाज्य गुणनखंड उसके वर्गमूल से बड़ा नहीं होता। पिछले उम्मीदवारों के कारण ये अभाज्य संख्याएँ सूची में पहले से हैं। किसी विभाजन में शेषफल शून्य हो तो उम्मीदवार अस्वीकार करें। यदि p > n / p होने तक कोई भाजक नहीं मिला, तो आगे परीक्षण विभाजन आवश्यक नहीं है। धनात्मक पूर्णांक विभाजन से वर्गमूल की शर्त व्यक्त होती है; p * p या फ़्लोटिंग-पॉइंट वर्गमूल निकालने की ज़रूरत नहीं पड़ती।
3. for &p in &primes सूची को उधार लेता है, क्रम से संदर्भ पाता है और हर usize मान को p में कॉपी करता है। नया अभाज्य केवल इस लूप के समाप्त होने के बाद जुड़ता है। अंत का for p in primes_up_to(1000) लौटाए गए वेक्टर से मान निकालकर छापता है। Rust के Vec दस्तावेज़ उधार लेकर किए गए इटरेशन और वेक्टर का स्वामित्व लेकर उसे उपभोग करने वाले इटरेशन में अंतर बताते हैं।
4. n <= max के अंदर max - n ऋणात्मक नहीं हो सकता। बची दूरी 2 से कम हो तो जोड़ने से पहले रुकें; अन्यथा n += 2 करें। इससे वृद्धि सीमा से आगे नहीं जाती।

उपयोग का दायरा

मूल प्रोग्राम स्थिर सीमा 1000 पर भी सही 168 अभाज्य संख्याएँ छापता है। लेकिन केवल सीमा को 0, 1 या 2 से बदलने पर दायरे से बाहर 2 या 3 छपता है, क्योंकि उम्मीदवार को परखने से पहले सीमा की जाँच नहीं होती। यहाँ दिया गया पुनः उपयोग योग्य फ़ंक्शन इन सीमांत स्थितियों को संभालता है।

सूची हर मिले अभाज्य के लिए एक usize सहेजती है। वेक्टर के मेटाडेटा और आवंटित क्षमता के लिए भी मेमोरी चाहिए। एक विभाजन को एक संक्रिया मानने पर विभाजनों की संख्या का एक मोटा ऊपरी बंध O(max sqrt(max)) है; यह मापा हुआ समय या बिट जटिलता नहीं है। बड़ी सीमाओं के लिए अधिक समय और संग्रहण चाहिए; मनमानी बड़ी सीमाओं तक तेज़ी से सूची बनाने की गारंटी नहीं है। बड़े अंतरालों के लिए एराटोस्थनीज की छलनी का लेख देखें। यह क्रिप्टोग्राफ़िक अभाज्य जनरेटर नहीं है।