Project Euler 7: 10001st prime

Problem 7 är det andra problemet med primtal och det första där vi ska hitta så pass många primtal att det behövs en effektiv algoritm för att finna primtal.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

Ett smidigt sätt att lösa detta problem är en primtalshov. Eftersom en riktig primtalshov är jobbig att implementera så har jag implementerat en enklare variant. Dock måste jag fortfarande veta ungefär hur många tal som ska in i hoven för att 10001 tal ska igenom den. Antalet primtal under talet X kan uppskattas med formeln antal_primtal = X/ln(X). Om X är 110 000 så får vi nästan 10000. Eftersom formeln inte är exakt så visade sig 110 000 räcka.

-module(problem_7).
-export([problem_7/0]).

problem_7() ->
    Start = os:timestamp(),
    Primes = primes(lists:seq(3,110000,2)),
    Res = lists:nth(10000, Primes),
    io:format("Resultatet är ~poch det tog ~p sekunder att beräkna~n", [Res, timer:now_diff(os:timestamp(), Start)/1000000]).

primes([]) -> [];
primes([H|T]) ->
    Sieved = [X || X <- T, X rem H =/= 0],
[H|primes(Sieved)].

Koden kan ni även hitta på github.