Sieve of Atkin implementation help

Not particularly related to rust but I am trying to write an idiomatic port of sieve of Atkin in Rust but as it seems, I am

  1. missing some non-prime numbers
  2. repeating a number?

Any help debugging the code would be greatly appreciated Rust Playground

fn square<T: std::ops::Mul<Output = T> + Copy>(arg: T) -> T {
    arg * arg
}

trait Flip {
    fn flip(&mut self);
}

impl Flip for bool {
    fn flip(&mut self) {
        *self = !*self
    }
}

fn prime_sieve(lim: usize) {
    if lim > 2 {
        print!("2, ");
    }
    if lim > 3 {
        print!("3, ");
    }

    let mut sieve = vec![false; lim];

    for x in (1..).take_while(|n| n * n < lim) {
        for y in (1..).take_while(|n| n * n < lim) {
            let n = 4 * square(x) + square(y);
            if n % 12 == 1 || n % 12 == 5 {
                sieve.get_mut(n).map(|b| {
                    b.flip();
                });
            }
            let n = 3 * square(x) + square(y);
            if n % 12 == 7 {
                sieve.get_mut(n).map(|b| {
                    b.flip();
                });
            }
            if x > y {
                let n = 3 * square(x) - square(y);
                if n % 12 == 11 {
                    sieve.get_mut(n).map(|b| {
                        b.flip();
                    });
                }
            }
        }
        (5..).take_while(|n| square(*n) < lim).for_each(|r| {
            if sieve.get(r) == Some(&true) {
                (square(r) .. lim).step_by(square(r)).for_each(|i| sieve.get_mut(i).map(|b| *b = false).unwrap());
            }
        });
        (5..lim).for_each(|i| {
            sieve.get(i).map(|b| {
                if *b {
                    if !primal::is_prime(i as u64) {
                        dbg!(i);
                    };
                }
            });
        });
    }
}

fn main() {
    prime_sieve(500);
}

Unlike the C++ implementation in the article you linked, you didn’t put the (5..) and (5..lim) loops outside of both the for y and for x loop.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.