use super::is_u64_prime;
use super::Prime;
#[derive(Clone)]
pub struct PrimeIter {
last_output: u64,
next_jump: u64,
}
impl PrimeIter {
pub fn from(n: u64) -> Self {
let last_output = if is_u64_prime(n) {
n - 1
} else {
n
};
let next_jump = if last_output < PrimeIter::PRIME_JUMPS.len() as u64 {
1
} else {
PrimeIter::PRIME_JUMPS[(n % (PrimeIter::PRIME_JUMPS.len() as u64)) as usize]
} as u64;
PrimeIter { last_output, next_jump }
}
pub fn all() -> Self {
Self::from(2)
}
const PRIME_JUMPS: [u8; 210] = [1, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3,
2, 1, 6, 5, 4, 3, 2, 1, 2, 1, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1,
6, 5, 4, 3, 2, 1, 2, 1, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 6, 5,
4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 8, 7, 6, 5,
4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1,
2, 1, 6, 5, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 2, 1,
6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 2];
}
pub struct CertIter {
pi: PrimeIter,
}
impl CertIter {
pub fn all() -> Self {
Self::from_pi(PrimeIter::all())
}
pub fn from(n: u64) -> Self {
Self::from_pi(PrimeIter::from(n))
}
pub fn from_pi(pi: PrimeIter) -> Self {
CertIter { pi }
}
}
impl From<PrimeIter> for CertIter {
fn from(pi: PrimeIter) -> Self {
CertIter::from_pi(pi)
}
}
impl Iterator for CertIter {
type Item = Prime;
fn next(&mut self) -> Option<Self::Item> {
self.pi.next().map(|n| unsafe { Prime::new_unsafe(n) })
}
}
#[test]
fn dump_jumps() {
use num::Integer;
let len = 210;
let mut v = Vec::new();
for i in 0_u64..len {
for j in 1..30 {
if (i + j).gcd(&len) == 1 {
v.push(j);
break;
}
}
}
{
let mut tot_jump = 0;
for i in 0..(v.len()/2) {
tot_jump += v[i*2 + 1];
}
println!("average jump len = {}", tot_jump as f64 / (len as f64) * 2.0);
}
println!("const PRIME_JUMPS: [u8; {}] = {:?};", len, v);
}
#[test]
fn dump_end() {
for p in (std::u64::MAX - 1000)..=std::u64::MAX {
if is_u64_prime(p) {
println!("{} (2^64 - {}) is prime", p, std::u64::MAX - p + 1);
}
}
}
#[test]
#[should_panic]
fn run_past_end() {
let start = std::u64::MAX - 1000;
let ps = PrimeIter::from(start);
let mut got_biggest = false;
for p in ps {
println!("got {}", p);
if got_biggest {
println!("Should not have gotten a prime after {}", super::MAX_U64_PRIME);
return;
}
if p == super::MAX_U64_PRIME {
got_biggest = true;
}
}
}
#[test]
fn check_includes_biggest() {
let start = std::u64::MAX - 1000;
let ps = PrimeIter::from(start);
for p in ps {
if p == super::MAX_U64_PRIME {
return;
}
}
panic!("Never got biggest u64 prime {}", super::MAX_U64_PRIME);
}
impl Iterator for PrimeIter {
type Item = u64;
fn next(&mut self) -> Option<Self::Item> {
loop {
let next_output = self.last_output + self.next_jump;
if next_output < self.last_output {
panic!("PrimeIter has overflowed past std::u64::MAX");
}
self.last_output = next_output;
self.next_jump =
if self.last_output < PrimeIter::PRIME_JUMPS.len() as u64 {
1
} else {
PrimeIter::PRIME_JUMPS[(self.last_output % (PrimeIter::PRIME_JUMPS.len() as u64)) as usize] as u64
};
if is_u64_prime(self.last_output) {
return Some(self.last_output);
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
const LIMIT: u64 = 1_000_000;
#[test]
fn compare_iter() {
use primal::Primes;
let mut ps1 = Primes::all().map(|n| n as u64).take_while(|n| n < &LIMIT);
let mut ps2 = PrimeIter::all().take_while(|n| n < &LIMIT);
loop {
let v1 = ps1.next();
let v2 = ps2.next();
assert_eq!(v1, v2, "Iterators were inconsistent");
if v1.is_none() {
break;
}
}
}
}