# [exercism] why does it not find the next prime

I have this code :

``````fn find_next_prime(start: u32) -> u32 {
let mut nbr = start;
let mut prime;

loop {
prime = true;
for i in 2..(nbr / 2 + 1) {
if nbr % i == 0 {
prime = false;
break;
}
}
if prime {
break;
}
nbr += 1;
}

nbr
}

pub fn nth(n: u32) -> u32 {
let mut found_prime = 0;
let mut count_found_primes = 0;

loop {
if count_found_primes == n {
return found_prime;
}
found_prime = find_next_prime(found_prime);
count_found_primes += 1;
}
}
``````

but for every n the answer is now 2.

any hints how to make this work ?

It's because in `find_next_prime` `nbr` starts off as `start`. And if `start` is already a prime, then it just returns that straight away. You'll probably have to add a `+1` somewhere so that you start searching for primes at the next number.

For these kinds of problems I can highly recommend the use of debuggers which allow you to inspect the value of all variables at runtime.
There exist a couple, depending on your editor or ice of choice

Then I think I have to see how I can make this work.
With 0 0 or 0 1 it also do not work

I use VS code
but I think I could better store all the found primes but this is not needed but I see no other way

There exist some algorithms for primality testing which are much faster than checking each value from 2..n.
Depending on your use case it might also be much much much faster computing a list of primes beforehand
These are obviously also a bit more complicated to implement.
First of all you could redactor your code a bit and extract a function that decides whether a given number is a prime or not.
Then you can test if that function works

After you have that function working you could easily get the nth prime by doing something like this:

``````(2..).filter(is_prime).nth(n).unwrap()
``````

Also your code does always return zero, because your first call to `find_next_prime` is with zero,one, or two always returns the input since the range `2..(nbr/2+1)` is empty.

oke, then I have to use a list where I store all earlier primes numbers.
And in my oponion there is not need to make a list of values I do not need.

But maybe I think the wrong way

If you really don't want to store a list you don't have to
If you are in a no_std environment and extremely memory limited your approach of testing each divisor and not storing anything might be appropriate. If hovewer you have a few byte to spare and a heap I would bet that any implementation saving primes in a vec and using them for the primality test is going to be much faster.
If you are in for a bit of more complicated code, there are some primality tests that are even faster and require no lists (just some constants) for values in the range of u64.
Miller–Rabin primality test - Wikipedia might be of interest, especially the subsection about deterministic variants.
If you interested and don't want to write it yourself here is the implementation of the miller test I wrote some time ago:
projecteuler/primes.rs at master · simon-auch/projecteuler · GitHub starting at line 278.

This is a working version of your code:

You were just 3 changes away from a working version

oke, I was more thinking about the sieve .

oke,

Then I have another problem.
The challenge is telling 0 is prime number 2

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

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

Also working..
Thanks all

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.