Primtalssætningen

Primtalssætningen anvendes til at beregne sandsynligheden for, at et tilfældigt valgt heltal er et primtal. Den forudsætter, at antallet af primtal mindre end x kan approksimeres med ${\displaystyle x/\ln(x)}$, ^[1] og den relative fejl ved denne approksimation bliver forsvindende når ${\displaystyle x}$ går mod uendelig. Denne sammenhæng anses for bevist i 1896 og bygger på Euklids modstridsbevis.

Det er muligt at beregne, hvor mange tal, der skal undersøges, før man med stor sandsynlighed har fundet et primtal. Hvis ambitionen er at finde et primtal med 100 cifre, skal der testes ${\displaystyle \log }$10¹⁰⁰ tal, dvs. 230.

Der findes dog stadig ikke en sikker metode til at afgøre, om et meget stort tal er et primtal, så der afholdes internationale konkurrencer iblandt computere om at afsløre det næste primtal i rækken. I slutningen af 2008 var det største kendte primtal 2^43.112.609-1. Tallet blev fundet den 23. august 2008 af GIMPS.

Noter

1. Hvor "ln" betegner den naturlige logaritme

Se også

• Primtal
• Wilsons sætning
• Eratosthenes' si

Eksterne henvisninger

• En grundig gennemgang på engelsk af primtal Arkiveret 7. juni 2004 hos Wayback Machine
• De 10.000 første primtal
• på svenska Arkiveret 11. november 2013 hos Wayback Machine