Regn

Spør Plingri:

Til kvadratrot
Tilbake

Lær

Javel, spør du, og hvordan kan du være så sikker på at 576460752303423433 er et primtall?

Jo, programmet mitt sjekker nemlig om det tallet som blir oppgitt er delelig med noen tall. Hvis det kun er delelig med 1 og seg selv, er det jo et primtall. Programmet gjør dette på en ganske effektiv måte: Først sjekker den om tallet delelig på 2, 3 eller 5. Hvis tallet ikke er delelig med noen av disse, fortsetter programmet med å sjekke om tallet er delelig med tall på formen 30n + 7, 30n + 11, 30n + 13, 30n + 17, 30n + 19, 30n + 23, 30n + 29 og 30n + 31 opp til og med kvadratroten av tallet.

Dette er tilstrekkelig, for hvis det er delelig på et annet tall mellom 30n + 1 og 30n + 31, er det også delelig med 2, 3 eller 5. (Sjekk dette!), og hvis det er delelig med et tall som er større en roten av tallet, må det også være delelig med et som er mindre. Ingen tall kan heller være delelig med et større tall enn seg selv.

Skriptet kjører på stud.ntnu-serveren, og den er ganske rask på gode dager. Jeg har lagt inn en begrensning på 19 siffer fordi det ville ta unødvendig lang tid å sjekke større tall. Man har allikevel funnet betraktelig større primtall (109433307*2⁶⁶⁴⁵²-1, med 20013 siffer), men det er på grunnlag av andre metoder som du kan lese mer om her.

© Børge Nordli 2001-2007