rust_algorithms/numbers/
primes.rs

1//! Tub sonlar bilan ishlash.
2
3/// `n` tub sonmi? — 6k±1 optimallashtirishli sinov bo'linishi.
4///
5/// **G'oya:** agar `n` ning `√n` dan katta bo'luvchisi bo'lsa, unga juft bo'lgan
6/// kichik bo'luvchi ham bo'ladi. Demak `√n` gacha tekshirish yetarli.
7/// Bundan tashqari, 3 dan katta har qanday tub son `6k−1` yoki `6k+1` ko'rinishda —
8/// shu sababli tekshiriladigan sonlar 3 barobar kam.
9///
10/// - **Time:** O(√n), **Space:** O(1).
11///
12/// # Misol
13/// ```
14/// use rust_algorithms::numbers::is_prime;
15///
16/// assert!(is_prime(97));
17/// assert!(!is_prime(1));
18/// assert!(!is_prime(91)); // 7 * 13
19/// assert!(is_prime(1_000_000_007));
20/// ```
21pub fn is_prime(n: u64) -> bool {
22    if n < 2 {
23        return false;
24    }
25    if n < 4 {
26        return true; // 2 va 3
27    }
28    if n % 2 == 0 || n % 3 == 0 {
29        return false;
30    }
31    let mut i = 5u64;
32    while i * i <= n {
33        if n % i == 0 || n % (i + 2) == 0 {
34            return false;
35        }
36        i += 6;
37    }
38    true
39}
40
41/// Eratosfen g'alviri — `n` gacha bo'lgan **barcha** tub sonlar.
42///
43/// **G'oya:** 2 dan boshlab, har bir tub sonning karralilarini "o'chirib" chiqamiz.
44/// O'chirish `p*p` dan boshlanadi, chunki undan kichiklari allaqachon o'chirilgan.
45///
46/// - **Time:** O(n log log n) — deyarli chiziqli!
47/// - **Space:** O(n) bit.
48///
49/// # Misol
50/// ```
51/// use rust_algorithms::numbers::sieve_of_eratosthenes;
52///
53/// assert_eq!(sieve_of_eratosthenes(30), vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29]);
54/// assert_eq!(sieve_of_eratosthenes(1).len(), 0);
55/// ```
56pub fn sieve_of_eratosthenes(n: usize) -> Vec<usize> {
57    if n < 2 {
58        return Vec::new();
59    }
60    let mut tub = vec![true; n + 1];
61    tub[0] = false;
62    tub[1] = false;
63
64    let mut p = 2usize;
65    while p * p <= n {
66        if tub[p] {
67            let mut k = p * p;
68            while k <= n {
69                tub[k] = false;
70                k += p;
71            }
72        }
73        p += 1;
74    }
75
76    tub.iter()
77        .enumerate()
78        .filter(|(_, &t)| t)
79        .map(|(i, _)| i)
80        .collect()
81}
82
83/// Har bir son uchun uning **eng kichik tub bo'luvchisi** (SPF) jadvali.
84///
85/// Bu jadval bilan istalgan `x <= n` ni O(log x) da ko'paytuvchilarga ajratish mumkin —
86/// ko'p so'rov bo'lganda [`prime_factors`] dan ancha tez.
87///
88/// # Misol
89/// ```
90/// use rust_algorithms::numbers::smallest_prime_factors;
91///
92/// let spf = smallest_prime_factors(10);
93/// assert_eq!(spf[9], 3);
94/// assert_eq!(spf[7], 7);
95/// ```
96pub fn smallest_prime_factors(n: usize) -> Vec<usize> {
97    let mut spf: Vec<usize> = (0..=n).collect();
98    let mut i = 2usize;
99    while i * i <= n {
100        if spf[i] == i {
101            let mut k = i * i;
102            while k <= n {
103                if spf[k] == k {
104                    spf[k] = i;
105                }
106                k += i;
107            }
108        }
109        i += 1;
110    }
111    spf
112}
113
114/// Sonni tub ko'paytuvchilarga ajratadi: `(tub_son, daraja)` juftliklari.
115///
116/// - **Time:** O(√n).
117///
118/// # Misol
119/// ```
120/// use rust_algorithms::numbers::prime_factors;
121///
122/// assert_eq!(prime_factors(360), vec![(2, 3), (3, 2), (5, 1)]); // 2³·3²·5
123/// assert_eq!(prime_factors(97), vec![(97, 1)]);
124/// assert_eq!(prime_factors(1), vec![]);
125/// ```
126pub fn prime_factors(mut n: u64) -> Vec<(u64, u32)> {
127    let mut out = Vec::new();
128    let mut d = 2u64;
129    while d * d <= n {
130        if n % d == 0 {
131            let mut daraja = 0;
132            while n % d == 0 {
133                n /= d;
134                daraja += 1;
135            }
136            out.push((d, daraja));
137        }
138        d += if d == 2 { 1 } else { 2 }; // 2 dan keyin faqat toq sonlar
139    }
140    if n > 1 {
141        out.push((n, 1));
142    }
143    out
144}
145
146#[cfg(test)]
147mod tests {
148    use super::*;
149
150    #[test]
151    fn is_prime_galvir_bilan_mos() {
152        let tublar = sieve_of_eratosthenes(10_000);
153        let mut idx = 0;
154        for n in 0..=10_000u64 {
155            let kutilgan = idx < tublar.len() && tublar[idx] as u64 == n;
156            assert_eq!(is_prime(n), kutilgan, "n = {n}");
157            if kutilgan {
158                idx += 1;
159            }
160        }
161    }
162
163    #[test]
164    fn katta_tub_sonlar() {
165        assert!(is_prime(2_147_483_647)); // Mersenne tub soni
166        assert!(!is_prime(2_147_483_646));
167    }
168
169    #[test]
170    fn kopaytuvchilarga_ajratish_qaytariladi() {
171        for n in 1u64..500 {
172            let ko = prime_factors(n);
173            let qayta: u64 = ko.iter().map(|&(p, e)| p.pow(e)).product();
174            assert_eq!(qayta, n, "n = {n}");
175            assert!(ko.iter().all(|&(p, _)| is_prime(p)));
176        }
177    }
178
179    #[test]
180    fn spf_jadvali() {
181        let n = 1000;
182        let spf = smallest_prime_factors(n);
183        for x in 2..=n {
184            let p = spf[x];
185            assert!(is_prime(p as u64), "spf[{x}] = {p} tub emas");
186            assert_eq!(x % p, 0);
187        }
188    }
189}
rust_algorithms/numbers/primes.rs

rust_algorithms/numbers/
primes.rs
