# Problem with nth prime number generator

I am working on Project Euler problem #7, to find the 10001th prime. Unfortunately, my code produces an incorrect answer. The 10001th prime it produces is low by around 700 (using an answer I found by searching the web) while the index for the correct prime is off by around 60. I suspect the problem lies in my test for primeness. Any help appreciated!

``````defmodule Prime do
def nth_prime(n) do
Stream.iterate(1, &(&1 + 2))
|> Stream.filter(&prime?(&1))
|> Stream.with_index(1)
|> Enum.find(fn {_prime, x} -> x == n end)
end

def prime?(2), do: true
def prime?(3), do: true
def prime?(4), do: false
def prime?(5), do: true
def prime?(n) do
limit = [7, round(:math.sqrt(n))] |> Enum.max
0 == Stream.iterate(3, &(&1 + 2))
|> Stream.take_while(fn x -> x < limit end)
|> Stream.filter(fn x -> rem(n,x) == 0 end)
|> Enum.to_list
|> Enum.count
end
end

IO.inspect Prime.nth_prime(10001)``````

I’ve only had a brief look, I can see a couple of areas to consider:

1. Prime.prime?(1) should return `false`, this looks like it returns `true`
2. `Stream.iterate(1, &(&1 + 2))` won’t generate a value `2`, which is actually a prime
3. I believe `Stream.take_while(fn x -> x < limit end)` should be `Stream.take_while(fn x -> x <= limit end)`; that is you should also consider the `limit`
1 Like

I think this is a working version of your code.

1. Need to ensure `2` is part of the generated stream since it is a prime
2. `Prime.prime?/1` previously considered `1`, `8`, and a few other anomalies to be prime
3. Also consider the `limit` in `prime?/1`
``````defmodule Prime do
def nth_prime(n) do
Stream.iterate(1, &(&1 + 1))
|> Stream.filter(&prime?(&1))
|> Stream.with_index(1)
|> Enum.find(fn {_prime, x} -> x == n end)
end

def prime?(1), do: false
def prime?(2), do: true
def prime?(3), do: true
def prime?(5), do: true
def prime?(7), do: true
def prime?(n) when rem(n, 2) == 0, do: false
def prime?(n) do
limit = [7, round(:math.sqrt(n))] |> Enum.max

Stream.iterate(3, &(&1 + 2))
|> Stream.take_while(fn x -> x <= limit end)
|> Stream.filter(fn x -> rem(n,x) == 0 end)
|> Enum.empty?
end
end
``````

(Editted to include @NobbZ’s excellent recommendation to use `Enum.empty?/1` which cleans up the code a lot and makes it a lot easier to reason about I think.)

2 Likes

As @kip already stated, your `Prime.prime?/1` considers `1` to be prime:

``````iex(2)> Prime.prime?(1)
true
``````

Also you are missing `2` as a prime (list of first 10 primes):

``````Stream.iterate(1, &(&1 + 2)) |> Stream.filter(&Prime.prime?/1) |> Enum.take(10)
[1, 3, 5, 7, 11, 13, 17, 19, 23, 29]
``````

Where you have `1` there should be a `2`. This in fact wont change the 10_001st prime though, as it is a single number that is wrong, everything thereafter seems to be correct on a first glance.

But the third observation by @kip seems to be goal-leeding. With that single line changed and after a felt-to-be hour I canceled the calculation, as some things you do are very costly.

1. Instead of `0 == s |> Enum.to_list |> Enum.count` you should use `s |> Enum.empty?`. This will safe you a lot of list allocations.
2. Instead of considering all odd numbers, you should probably use a wheel sieve. (except for 2 and 3, all known primes are either `k * 5 + 1` or `k * 5 - 1` where `k` is any natural number but 0.
3. Instead of creating a list of all odd divisors of a number, you should probably use `Enum.any?` to cancel on the very first divisor found. (has roughly the same effect as piping the filtered stream to `Enum.empty?/1`)
4. Instead of adding an index and to each element, simply dropping `n - 1` elements might decrease runtime as well, but not as drastically as eg. improving the `prime?/1`.

My personal solution runs in about 7.5 seconds on my machine. So you have quite some way to go to reach the 60 seconds goal 1 Like

Ouch… Just checked @kip’s solution he posted in the meantime. It returned nearly instantly… Perhaps I have overcomplicated my solution 1 Like

Thanks for your help, Kip & NobbZ! Much appreciated!