How to remove element from a index of a vector?


#1

Hello. i’m trying to implement Sieve of Eratosthenes.

///Problem 03: Sieve of Eratosthenes

///Vectors, iteration mutability

pub fn sieve(n: u32) -> Vec<u32> {
    let mut vector: Vec<u32> = Vec::new();
    for x in 2..n {
        vector.push(x);
    }
    for x in &vector {
        for y in &vector {
            if *y % *x == 0{
                vector.remove(y)
            }
        }
    }
    vector
}

but i’m not able to remove element from vector. please help.


#2

Please post the particular error message(s) you’re having trouble with.

The first problem is a type error caused by remove taking an index of the element to remove, not the element itself. Using indices also solves the borrowing problems, and is the typical way to iterate over a vector in this manner:

for x in 0..vector.len() {
    for y in 0..vector.len() {
        if vector[y] % vector[x] == 0 {
            vector.remove(y);
        }
    }
}

This should compile, but will almost certainly not work, I believe it will crash with an index out of bounds error, and, if that is fixed in the most obvious way, every number will end up being removed.

However a better way to solve this particular problem would be to use a true Sieve of Eratosthenes: a major reason implementations can be so far is that it avoids performing a lot of % operations by knowing automatically when something will have a factor.

A good place to start is with let mut is_prime: Vec<bool> = vec![true; n];, where true indicates that a number is prime, which can then be optimised and optimised.