Opgaven lyder som følgende:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143?
For at vi kan løse dette problem kræver det først og fremmest at vi kan generere rækken af primtal eller i hvert fald forstå genereringen. Lad os få slået fast, hvad er et primtal? Et primtal er kort sagt er et positivt heltal som kun er deleligt med 1 og tallet selv.
Her er de første 50 primtal:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229
Læg især mærke til at 2 er det eneste lige primtal – alle primtal efter 2 (indtil videre bevist) er ulige. Leonhard Euler, deraf Project Euler, har bevist at rækken af primtal går mod uendelig.
Et primtal kan findes med eksempelvis Eratosthenes’ si - ældgammel algoritme som er let at forstå og som netop fastlægger alle primtal for os. Udviklet af Eratosthenes, græsk astronom og matematiker, 274 f.Kr – 194 f.Kr.
Lad os se nærmere på algoritmen med udgangspunkt i Project Euler problemet:
Mens divisor*divisor < grænseværdi
- Lad p = 2 (første primtal)
- Fyld sien op med tal større end 1.
- Fjern alle tal med divisor 2 undtagen 2 (2 er et primtal).
- Find næste tal k efter p og erstat p med k+1.
- Gentag step 3 og 4 indtil p*p > grænseværdi.
Lad os se implementeringen i C#:
public static List<int> SieveOfEratosthene(List<int> numbers)
{
int p = 2;
int k = 0;
while (p * p < numbers.Max())
{
for (int i = k + 1; i < numbers.Count(); i++)
if (numbers[i] % p == 0)
numbers.RemoveAt(i);
p = numbers[k++];
}
return numbers;
}
På en Windows 7 32 bit maskine med 4GB RAM kan denne implementering finde alle primtal i talrækken 2 og 134217728. Dette skyldes at vi ikke kan allokere mere end det på heapen. Hvis vi derimod brugte et int[] array, så ville vi, på samme maskine, kunne lagre cirka 360M heltal på stakken.
Jeg har ikke forsøgt på en 64 bit maskine, men umiddelbart ville vores referencerne til vores generiske int liste på heapen formindske vores hukommelsesallokering og give os endnu mindre plads. Hukommelsesallokeringen på stakken må være uændret. Jeg kommer ind på hukommelsesallokering i næste afsnit af min serie af grundlæggende principper og begreber i .NET, så lad os vente med at gå mere i dybden med det nu.
Denne implementering er derfor ikke brugbar til dette problem, i hvert fald ikke, hvis vi vil finde alle primtal op til vores grænse på 600851475143 for så derefter at finde frem til divisorerne.
Lad os derfor forbedre algoritmen og introducere begrebet trial division.
Trial division er en simpel og naiv algoritme til at finde primtal som er divisorer til et tal n med samtlige tal m <= √grænse. Jo større afstand mellem n og grænsen, desto større usikkerhed, men hurtigere. Jo mindre afstand mellem n og grænsen, jo større sikkerhed, men selvfølgelig langsommere.
Lad os se nærmere på algoritmen:
- Vælg tal n
- Dividere tallet n med alle tal m <= √grænse
- Hvis tallet m er divisor til n, så har vi et primtal.
Vi kan derfor begrænse vores grænse til k <= √grænse – dvs. at vi nu kun har behov for 775146 pladser og derfor er udenfor begrænsningen i .NET nævnt tidligere.
Vi har nu gennemgået både Eratosthenes’ si og trial division og med den viden kan vi nu lave en hurtig og sikker algoritme som opfylder netop vores behov:
private static List<long> FindPrimeNumbers(long n)
{
List<long> primes = new List<long>();
for(long i=2;i<=n;i++)
{
if (n % i == 0)
{
primes.Add(i);
n /= i;
i = 2;
}
if (primes.Count > 0 && primes.Aggregate((p, q) => p * q) == n)
break;
}
return primes;
}
static void Main(string[] args)
{
int result = FindPrimeNumbers(600851475143).Max();
}
Lad os se nærmere på algoritmen. FindPrimeNumbers() tager vores tal n som parameter. For hvert tal op til vores grænse, tallet n, kontrollere vi om tallet i er divisor for n. Hvis det er tilfældet, så tilføjer vi divisoren i til vores primtalssamling.
Vi kan derefter dividere vores tal n med den nyfundne divisor i. Da der ingen mindre divisorer findes end i kan vi derfor antage at i er et primtal og dividere hvert i ud. Vi starter derefter forfra med søgningen efter næste primtal. Hvis den samlede sum af vores fundne primtal er lig med vores tal n har vi fundet de primtal som går op i tallet. Vi kan nu tage det højeste primtal fra samlingen.
Det højeste primtal i samlingen og løsningen på problemet er derfor: 6857.
