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)
Need to ensure 2 is part of the generated stream since it is a prime
Prime.prime?/1 previously considered 1, 8, and a few other anomalies to be prime
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.)
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.
Instead of 0 == s |> Enum.to_list |> Enum.count you should use s |> Enum.empty?. This will safe you a lot of list allocations.
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.
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)
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
