Why does this not work. Tests are erroring out

help
1 
mod np {
    pub fn nth(n: u32) -> u32 {
        let mut found_primes: Vec<u32> = vec![];
        let mut number = 2;

        while found_primes.len() <= n as usize {
            if is_prime(number) {
                found_primes.push(number)
            }

            number = number + 1
        }

        return number;
    }

    pub fn is_prime(n: u32) -> bool {
        let upper_bound = (n as f32).sqrt().ceil() as u32;
        for x in 1..=upper_bound {
            if n % x == 0 {
                return false;
            }
        }

        return true;
    }
}

#[test]
fn test_first_prime() {
    assert_eq!(np::nth(0), 2);
}

#[test]
fn test_second_prime() {
    assert_eq!(np::nth(1), 3);
}

(Playground)

test test_sixth_prime ... ignored
test test_first_prime ... test test_first_prime has been running for over 60 seconds
test test_first_prime ... FAILED

failures:

---- test_first_prime stdout ----
thread 'test_first_prime' panicked at 'attempt to add with overflow', src\lib.rs:10:18
note: Run with `RUST_BACKTRACE=1` environment variable to display a backtrace.


failures:
    test_first_prime
2

is_prime always returns false because the first check is for if the number is divisible by 1, which all numbers are. Since you're looping until you find the first true result, that will never terminate, and your tests fail after timing out. If you change it to for x in 2..upper_bound, it will no longer time out.

3

thanks, changed it and now all the tests are failing

---- test_first_prime stdout ----
thread 'test_first_prime' panicked at 'assertion failed: `(left == right)`
  left: `4`,
 right: `2`', tests\nth-prime.rs:5:5
note: Run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

---- test_second_prime stdout ----
thread 'test_second_prime' panicked at 'assertion failed: `(left == right)`
  left: `6`,
 right: `3`', tests\nth-prime.rs:10:5
4

is_prime isn't a correct check of primality; it says that 1 is prime but 2 isn't, which is messing up your checks.

5

oke

with this code all my tests are green but I think there could be a lot of improvements,

pub fn nth(n: u32) -> u32 {
    let mut found_primes : Vec<u32> = vec![]; 
    let mut number = 2; 

    while found_primes.len() < n as usize {
        if is_prime(number){
            found_primes.push(number)
        }

        number = number + 1;
    }

    match found_primes.pop() {
        Some(v) => return v ,
        None    => return 2 
    }

}

pub fn is_prime(n: u32) -> bool {
    let upper_bound = (n as f32).sqrt().ceil() as u32;
    for x in 2..=upper_bound{
      if n % x == 0
      {
          return false; 
      }   
    }

    return true;

}
6

Here's a version:

pub fn nth(n: u32) -> u32 {
    // Iterator is (essentially) infinite, so unwrap is OK
    (1..).filter(|i| is_prime(*i)).nth(n as usize).unwrap()
}

pub fn is_prime(n: u32) -> bool {
    // Handle 2's sqrt rounding up to 2
    let upper_bound = std::cmp::min((n as f32).sqrt().ceil() as u32, n - 1);
    // True only if all numbers up to sqrt aren't divisible
    // and also number is greater than 1 (treating 0 and 1 as special)
    (2..=upper_bound).all(|i| n % i != 0) && n > 1
}

This avoids making a list of primes.

2 Likes
7

Thanks, I like it a lot. It is almost the way I would solve it in Haskell where you use a lot of lazy evaluation.
the only thing I do not see it the upperbound one. Am I right that you compare the sqrt of a number and the n number - 1 which is the lowest number.

Roelof

8

The upper bound of the divisors to check is the minimum of the square root of the number rounded up, or one below the number. If you didn't take the minimum, if you ran is_prime on 2, you'd get the upper bound to be ceil(sqrt(2)), which is 2 - and since 2 is divisible by itself, the function would return that 2 was not prime.

9

Thanks for the explanation. Learned a lot this way but still a lot to learn.

10

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.