Ett problem med ett stort primtal och en lösning utan primtalshov!
The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^6972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p−1, have been found which contain more digits.
However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×2^7830457+1.
Find the last ten digits of this prime number.
Det finns två viktiga egenskaper hos erlang att tänka på när man löser detta problem:
Det finns ingen övre gräns på hur stora tal man får ha i erlang.
math:pow(X, Y) har optimerats på ett sätt som gör den opålitlig om man använder för stora tal.
Istället för att beräkna 2^7830457 så kan vi beräkna 1024^783045*2^7, på så vis så behöver vi endast göra en dryg tiondel så många beräkningar. Utöver det så behöver vi inte siffrorna som är för stora för att påverka resultatet, vi kan alltså använda modulo efter varje steg.
problem_97() -> Start = os:timestamp(), Res = (28433 * pow2(1,0) + 1) rem 10000000000, io:format("Resultatet: ~p och det tog ~p sekunder att beräkna~n", [Res, timer:now_diff(os:timestamp(), Start)/1000000]). pow2(N, 7830450) -> pow3(N, 7830450); pow2(N, Count) -> pow2((N*1024 rem 10000000000), Count+10). pow3(N, 7830457) -> N; pow3(N, Count) -> pow3((N*2 rem 10000000000), Count+1).
Projekt Euler med André Le Blanc 