Project Euler

Project Euler probleem 51

Bekijk het originele probleem op Project Euler

Probleemstelling kort

In dit probleem zoek je het kleinste priemgetal dat deel uitmaakt van een familie van acht priemgetallen.

Die familie ontstaat door op dezelfde posities in het getal cijfers te vervangen door telkens hetzelfde cijfer.

Algoritme

Ik heb een brute force algoritme geschreven waar dat je elke getal onder de miljoen gaat controleren of er een getal is dat een family heeft met minstens 8 priemgetallen.

Je gaat hierin een kleine bitmask trucje implementeren zodanig je eenvoudig alle posities van je getal kan veranderen op basis van de binaire voorstelling van een getal.

Voorbeeld:

stel als je een getal pakt met een lengte van 123456 die getal heeft een lengte van 6.

Een trucje om alle waarde te implementeren is als volgt.

Je gaat elke getal tussen [1 (000001) en 63 (111111)] in binaire waarde voorstellen.

(63 komt van het feit dat 2 tot de 6de gelijk is aan 64 - 1. Dus stel als je cijfer een lengte heeft van 5 dan ga je van 1 tot en met 2 tot de 5de - 1, dus steeds van 1 tot 2 tot de Nde - 1 waar dat N gelijk is aan de lengte van het getal.)

Bv het getal 41 zijn binaire voorstelling is 101001.

Wat je als volgt gaat doen is controleren op welke plaatsen een nul staat en op de plekken waar een 0 staat ga je op al die plekken een getal tussen [0, 9] zetten.

En dan ga je voor elke nieuwe gecreëerde waarde controleren of het een priemgetal is.

En vanaf je een waarde tegenkomt dat een familie van 8 priemgetallen heeft dan stop je.

En alle priemgetallen onder de miljoen worden ook voorhand eenmalig berekent met de zeef van eratosthenes zodanig dat je niet steeds een getal opnieuw moet controleren of het een priemgetal is of niet.

De code is als volgt:

Oplossing: 121313
Uitvoeringstijd: 0.088596 seconden