133

I'm trying to compute the 10,001st prime in Rust (Project Euler 7), and as a part of this, my method to check whether or not an integer is prime references a vector:

fn main() {
    let mut count: u32 = 1;
    let mut num: u64 = 1;
    let mut primes: Vec<u64> = Vec::new();
    primes.push(2);

    while count < 10001 {
        num += 2;
        if vectorIsPrime(num, primes) {
            count += 1;
            primes.push(num);
        }
    }
}

fn vectorIsPrime(num: u64, p: Vec<u64>) -> bool {
    for i in p {
        if num > i && num % i != 0 {
            return false;
        }
    }

    true
}

When I try to reference the vector, I get the following error:

error[E0382]: use of moved value: `primes`
 --> src/main.rs:9:31
  |
9 |         if vectorIsPrime(num, primes) {
  |                               ^^^^^^ value moved here, in previous iteration of loop
  |
  = note: move occurs because `primes` has type `std::vec::Vec<u64>`, which does not implement the `Copy` trait

What do I have to do to primes in order to be able to access it within the vectorIsPrime function?

2
  • Orthogonal to the question: 1) Always useful to share the rust-playground link. 2) The logic is incorrect (count +=1) should happen outside.
    – Coder
    Nov 5, 2021 at 21:05
  • 1
    @Coder 2) count is holding the value of number of primes, so it should be inside the block :) May 13 at 14:54

3 Answers 3

124

With the current definition of your function vectorIsPrime(), the function specifies that it requires ownership of the parameter because you pass it by value.

When a function requires a parameter by value, the compiler will check if the value can be copied by checking if it implements the trait Copy.

  • If it does, the value is copied (with a memcpy) and given to the function, and you can still continue to use your original value.
  • If it doesn't, then the value is moved to the given function, and the caller cannot use it afterwards

That is the meaning of the error message you have.

However, most functions do not require ownership of the parameters: they can work on "borrowed references", which means they do not actually own the value (and cannot for example put it in a container or destroy it).

fn main() {
    let mut count: u32 = 1;
    let mut num: u64 = 1;
    let mut primes: Vec<u64> = Vec::new();
    primes.push(2);

    while count < 10001 {
        num += 2;
        if vector_is_prime(num, &primes) {
            count += 1;
            primes.push(num);
        }
    }
}

fn vector_is_prime(num: u64, p: &[u64]) -> bool {
    for &i in p {
        if num > i && num % i != 0 {
            return false;
        }
    }
    true
}

The function vector_is_prime() now specifies that it only needs a slice, i.e. a borrowed pointer to an array (including its size) that you can obtain from a vector using the borrow operator &.

For more information about ownership, I invite you to read the part of the book dealing with ownership.

4
  • Why does i in for &i in p{ require an & in front of it? The code throws a compile error without it, and I'm curious as to why.
    – mjkaufer
    Mar 1, 2015 at 23:40
  • 2
    @mjkaufer, it means that i is a reference, and so therefore, in the loop, i will be the value, rather than a reference. if you leave it out, you'd need *i's when doing the comparisons. Mar 2, 2015 at 0:56
  • The prime testing condition in vector_is_prime is incorrect, it should be: if num > i && num % i == 0
    – fr1550n
    Jul 14, 2020 at 9:45
  • I have the same issue but using & did not solve rust impl Draggable2 { pub(crate) fn __init__(mut self) { &self.drag_handler(); //TODO &self.drag_over_handler(); } Error rust &self.drag_handler(); | -------------- `self` moved due to this method call
    – Ali Husham
    Apr 16, 2022 at 9:46
73

Rust is, as I would say, a “value-oriented” language. This means that if you define primes like this

let primes: Vec<u64> = …

it is not a reference to a vector. It is practically a variable that stores a value of type Vec<u64> just like any u64 variable stores a u64 value. This means that if you pass it to a function defined like this

fn vec_is_prime(num: u64, vec: Vec<u64>) -> bool { … }

the function will get its own u64 value and its own Vec<u64> value.

The difference between u64 and Vec<u64> however is that a u64 value can be easily copied to another place while a Vec<u64> value can only move to another place easily. If you want to give the vec_is_prime function its own Vec<u64> value while keeping one for yourself in main, you have to duplicate it, somehow. That's what's clone() is for. The reason you have to be explicit here is because this operation is not cheap. That's one nice thing about Rust: It's not hard to spot expensive operations. So, you could call the function like this

if vec_is_prime(num, primes.clone()) { …

but that's not really what you want, actually. The function does not need its own a Vec<64> value. It just needs to borrow it for a short while. Borrowing is much more efficient and applicable in this case:

fn vec_is_prime(num: u64, vec: &Vec<u64>) -> bool { …

Invoking it now requires the “borrowing operator”:

if vec_is_prime(num, &primes) { …

Much better. But we can still improve it. If a function wants to borrow a Vec<T> just for the purpose of reading it, it's better to take a &[T] instead:

fn vec_is_prime(num: u64, vec: &[u64]) -> bool { …

It's just more general. Now, you can lend a certain portion of a Vec to the function or something else entirely (not necessarily a Vec, as long as this something stores its values consecutively in memory, like a static lookup table). What's also nice is that due to coersion rules you don't need to alter anything at the call site. You can still call this function with &primes as argument.

For String and &str the situation is the same. String is for storing string values in the sense that a variable of this type owns that value. &str is for borrowing them.

3
  • One minor detail: When iterating, it seems that, as @Vaelden wrote, the iterating variable, i, needs to be written as &i.
    – mjkaufer
    Mar 1, 2015 at 23:39
  • @mjkaufer: That's one possibility, yes. Another would be to dereference i where you use it.
    – sellibitze
    Mar 1, 2015 at 23:44
  • Iterating over a borrowed slice gives you borrowed elements. Doing it differently would require the element type to be Copy or Clone. If you use &i in the for loop, i will be a copy of a vector's element.
    – sellibitze
    Mar 1, 2015 at 23:51
10

You move value of primes to the function vectorIsPrime (BTW Rust use snake_case by convention). You have other options, but the best one is to borrow vector instead of moving it:

fn vector_is_prime(num: u64, p: &Vec<u64>) -> bool { … }

And then passing reference to it:

vector_is_prime(num, &primes)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.