My prime number sieve is extremely slow even with --release

Question

I have looked at multiple answers online to the same question but I cannot figure out why my program is so slow. I think it is the for loops but I am unsure.

P.S. I am quite new to Rust and am not very proficient in it yet. Any tips or tricks, or any good coding practices that I am not using are more than welcome :)

math.rs

pub fn number_to_vector(number: i32) -> Vec<i32> {
    let mut numbers: Vec<i32> = Vec::new();

    for i in 1..number + 1 {
        numbers.push(i);
    }

    return numbers;
}

user_input.rs

use std::io;

pub fn get_user_input(prompt: &str) -> i32 {
    println!("{}", prompt);

    let mut user_input: String = String::new();

    io::stdin().read_line(&mut user_input).expect("Failed to read line");

    let number: i32 = user_input.trim().parse().expect("Please enter an integer!");

    return number;
}

main.rs

mod math;
mod user_input;

fn main() {
    let user_input: i32 = user_input::get_user_input("Enter a positive integer: ");
    let mut numbers: Vec<i32> = math::number_to_vector(user_input);
    numbers.remove(numbers.iter().position(|x| *x == 1).unwrap());
    let mut numbers_to_remove: Vec<i32> = Vec::new();

    let ceiling_root: i32 = (user_input as f64).sqrt().ceil() as i32;

    for i in 2..ceiling_root + 1 {
        for j in i..user_input + 1 {
            numbers_to_remove.push(i * j);
        }
    }

    numbers_to_remove.sort_unstable();
    numbers_to_remove.dedup();
    numbers_to_remove.retain(|x| *x <= user_input);

    for number in numbers_to_remove {
        if numbers.iter().any(|&i| i == number) {
            numbers.remove(numbers.iter().position(|x| *x == number).unwrap());
        }
    }

    println!("Prime numbers up to {}: {:?}", user_input, numbers);
}

Answer 1

There's two main problems in your code: the i * j loop has wrong upper limit for j, and the composites removal loop uses O(n) operations for each entry, making it quadratic overall.

The corrected code:

fn main() {
    let user_input: i32 = get_user_input("Enter a positive integer: ");
    let mut numbers: Vec<i32> = number_to_vector(user_input);
    numbers.remove(numbers.iter().position(|x| *x == 1).unwrap());
    let mut numbers_to_remove: Vec<i32> = Vec::new();
    let mut primes: Vec<i32> = Vec::new();     // new code
    let mut i = 0;                             // new code

    let ceiling_root: i32 = (user_input as f64).sqrt().ceil() as i32;

    for i in 2..ceiling_root + 1 {
        for j in i..(user_input/i) + 1 {       // FIX #1:  user_input/i
            numbers_to_remove.push(i * j);
        }
    }

    numbers_to_remove.sort_unstable();
    numbers_to_remove.dedup();
    //numbers_to_remove.retain(|x| *x <= user_input);   // not needed now
    
    for n in numbers {                         // FIX #2:
        if n < numbers_to_remove[i] {          //   two linear enumerations
            primes.push(n);              
        }
        else {
            i += 1;                            //   in unison
        }
    }
    
    println!("Last prime number up to {}: {:?}", user_input, primes.last());
    println!("Total prime numbers up to {}: {:?}", user_input, 
         primes.iter().count());
}

Your i * j loop was actually O( N^1.5), whereas your numbers removal loop was actually quadratic -- remove is O(n) because it needs to move all the elements past the removed one back, so there is no gap.

The mended code now runs at ~ N^1.05 empirically in the 10⁶...2*10⁶ range, and orders of magnitude faster in absolute terms as well.

Oh and that's a sieve, but not of Eratosthenes. To qualify as such, the is should range over primes, not just all numbers.

Answer 2

As commented AKX you function's big O is (m * n), that's why it's slow.

For this kind of "expensive" calculations to make it run faster you can use multithreading.

This part of answer is not about the right algorithm to choose, but code style. (tips/tricks)

I think the idiomatic way to do this is with iterators (which are lazy), it make code more readable/simple and runs like 2 times faster in this case.

fn primes_up_to() {
    let num = get_user_input("Enter a positive integer greater than 2: ");
    let primes = (2..=num).filter(is_prime).collect::<Vec<i32>>();

    println!("{:?}", primes);
}

fn is_prime(num: &i32) -> bool {
    let bound = (*num as f32).sqrt() as i32;
    *num == 2 || !(2..=bound).any(|n| num % n == 0)
}

Edit: Also this style gives you ability easily to switch to parallel iterators for "expensive" calculations with rayon (Link)

Edit2: Algorithm fix. Before, this uses a quadratic algorithm. Thanks to @WillNess