Last active
August 21, 2019 21:48
-
-
Save Mathspy/fb47758874f01dc63d8a609b5486105e to your computer and use it in GitHub Desktop.
All the prime numbers your heart desires in Rust!
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Use this if you want [2, 3, 5.....] | |
use std::collections::HashMap; | |
/// This is a prime number generator based on [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) | |
/// that can be _trivially_ improved by switching to [Sieve of Atkin](https://en.wikipedia.org/wiki/Sieve_of_Atkin) for extra speed | |
struct PrimeIterator { | |
current: u64, | |
composite_to_primes: HashMap<u64, Vec<u64>>, | |
} | |
impl PrimeIterator { | |
fn new() -> Self { | |
PrimeIterator { | |
current: 1, | |
composite_to_primes: HashMap::new(), | |
} | |
} | |
} | |
impl Iterator for PrimeIterator { | |
type Item = u64; | |
// Algorithm based on this stackoverflow answer: | |
// https://stackoverflow.com/questions/567222/simple-prime-generator-in-python | |
fn next(&mut self) -> Option<Self::Item> { | |
self.current += 1; | |
if let Some(primes) = self.composite_to_primes.get(&self.current) { | |
for prime in primes.clone() { | |
self.composite_to_primes | |
.entry(self.current + prime) | |
.or_insert(Vec::new()) | |
.push(prime); | |
} | |
self.composite_to_primes.remove(&self.current); | |
self.next() | |
} else { | |
self.composite_to_primes | |
.insert(self.current * self.current, vec![self.current]); | |
Some(self.current) | |
} | |
} | |
} | |
fn main() { | |
assert_eq!( | |
PrimeIterator::new().take(100).collect::<Vec<u64>>(), | |
vec![ | |
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, | |
89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, | |
181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, | |
277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, | |
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, | |
487, 491, 499, 503, 509, 521, 523, 541 | |
] | |
); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Use this if you want [INPUT......] | |
/// This is a prime number generator based on a [simple primality test described on Wikiedpa](https://en.wikipedia.org/wiki/Primality_test#Pseudocode) | |
/// that can be _trivially_ improved by switching is_prime implementation to [AKS_primality_test](https://en.wikipedia.org/wiki/AKS_primality_test) for extra speed | |
struct PrimeIterator { | |
current: u64, | |
} | |
impl PrimeIterator { | |
fn new() -> Self { | |
PrimeIterator { current: 1 } | |
} | |
fn from(start: u64) -> Self { | |
PrimeIterator { current: start - 1 } | |
} | |
} | |
impl Iterator for PrimeIterator { | |
type Item = u64; | |
fn next(&mut self) -> Option<Self::Item> { | |
loop { | |
self.current += 1; | |
if is_prime(self.current) { | |
return Some(self.current); | |
} | |
} | |
} | |
} | |
fn is_prime(potentially_prime: u64) -> bool { | |
if potentially_prime <= 3 { | |
return potentially_prime > 1; | |
} | |
if potentially_prime % 2 == 0 || potentially_prime % 3 == 0 { | |
return false; | |
} | |
let mut i = 5; | |
while i * i <= potentially_prime { | |
if potentially_prime % i == 0 || potentially_prime % (i + 2) == 0 { | |
return false; | |
} | |
i += 6; | |
} | |
true | |
} | |
fn main() { | |
assert_eq!( | |
PrimeIterator::new().take(100).collect::<Vec<u64>>(), | |
vec![ | |
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, | |
89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, | |
181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, | |
277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, | |
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, | |
487, 491, 499, 503, 509, 521, 523, 541 | |
] | |
); | |
assert_eq!( | |
PrimeIterator::from(1000).take(100).collect::<Vec<u64>>(), | |
vec![ | |
1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, | |
1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, | |
1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, | |
1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, | |
1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, | |
1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, | |
1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, | |
1709, 1721, | |
] | |
); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment