Primtal

Din uppgift är att skriva en funktion som returnerar en lista av alla primtal från 2 till något tal p som ges som argument till funktionen.  Du skall göra tre lösningar och sen undersöka om det är någon skillnad i körtider mellan de tre versionerna. Alla versionerna är en implementering av Eratosthenes såll. 

Den första lösningen

Skapa en lista med alla heltal mellan 2 och det givna talet n. Du kan använda anropet Enum.to_list(2..n) för att skapa listan av tal.  Det första talet i listan är ett primtal och det skall vara det första talet i den lista som vi genererar. Plocka nu bort alla tal i resten av listan som är delbara med det första talet, använd funktionen rem/2.  Om resultatet är en tom lista så är vi klara i annat fall har du hittat nästa primtal.

Den andra lösningen

Som i den första lösningen skall du skapa en lista med alla heltal mellan 2 och det givna talet n. Skapa också en lista med alla primtal som du hittat, vilket naturligtvis till en början är en tom lista. Plocka talen från listan med alla tal, ett och ett,  och kontroller om det är delbart med något av de primtal som du hittat. Om det är delbart med ett primtal kastar vi bort det men om det inte är delbart med något primtal så har vi hittat ett nytt primtal som du lägger sist i listan av primtal. När du inte har några tal kvar så har du hittat alla primtal.

Den tredje lösningen

Den tredje lösningen är identisk med den andra lösningen med den skillnaden att när vi hittar ett primtal så lägger vi det först i listan av primtal. När vi inte har några tal kvar tar vi och vänder på listan av primtal så att de kommer i nummerordning.