6XC

Priemgetallenlijst & controle

Lijst alle priemgetallen in een bereik (zeef van Eratosthenes), of controleer of een enkel getal een priemgetal is — direct resultaat.

1.050 weergaven

Hoe Het Werkt

De tool wisselt tussen twee verschillende algoritmen, elk geschikt voor een andere vraag. Lijstmodus vindt alle priemgetallen tot een limiet met de Zeef van Eratosthenes, een van de oudste algoritmen die nog dagelijks worden gebruikt (toegeschreven aan de Griekse wiskundige Eratosthenes, 3e eeuw v.Chr.). Beginnend bij 2 worden alle veelvouden van 2 gemarkeerd als samengesteld, daarna gaat men naar het volgende ongemarkeerde getal (3) en markeert al zijn veelvouden, dan het volgende ongemarkeerde getal (5), enzovoort. Wat ongemarkeerd blijft zodra u de vierkantswortel van de limiet bereikt, is een priemgetal. Een klein voorbeeld: om tot 30 te zeven, streept u eerst de veelvouden van 2 door (4,6,8,…), dan de veelvouden van 3 (6,9,12,…, sommige al doorgestreept), dan de veelvouden van 5 (10,15,…) — omdat 5×5=25 ≤ 30 maar 7×7=49 > 30, kunt u daar stoppen; wat overblijft — 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — is de volledige lijst. Dit draait in O(n log log n)-tijd, wat betekent dat het snel blijft zelfs als het bereik oploopt tot honderdduizenden.

Controlemodus beantwoordt een andere vraag — is dit specifieke getal een priemgetal? — met proefdeling tot aan de vierkantswortel. Om te testen of n een priemgetal is, volstaat het delers te controleren van 2 tot en met √n. De redenering: als n = a × b, met zowel a als b groter dan √n, dan zou a × b groter zijn dan n, wat onmogelijk is. Dus minstens een van de twee factoren moet √n of kleiner zijn, en die wordt gevonden voordat de lus eindigt. Voorbeeld: om 97 te controleren hoeft u alleen deelbaarheid door 2, 3, 5, 7 te testen (want 9² = 81 ≤ 97 maar 10² = 100 > 97) — geen ervan deelt gelijk, dus 97 is een priemgetal.

Wat U Moet Weten

De twee modi bestaan omdat ze verschillende afwegingen maken: de zeef is efficiënt voor het produceren van veel priemgetallen tegelijk, maar verspilt geheugen en tijd als u alleen geïnteresseerd bent in één getal dicht bij een enorme limiet; proefdeling is efficiënt voor een enkele controle, maar veel te traag als het herhaald wordt voor elk getal in een groot bereik, één voor één. De juiste kiezen voor de klus is precies waarom deze tool beide aanbiedt.

  • 1 wordt per definitie en conventie uitgesloten van de priemgetallen — het heeft slechts één deler, geen twee, wat de uniciteit van priemfactorontbinding zou doorbreken als het werd toegelaten.
  • 2 is het enige even priemgetal; elk ander even getal is deelbaar door 2 en dus samengesteld.
  • Naarmate getallen groter worden, worden priemgetallen gemiddeld zeldzamer, maar ze houden nooit op te verschijnen — Euclides bewees meer dan tweeduizend jaar geleden dat er oneindig veel zijn.

Veelgestelde vragen

Wat telt als een priemgetal?

Een natuurlijk getal groter dan 1 met precies twee positieve delers: 1 en zichzelf. 1 is geen priemgetal omdat het maar één deler heeft, en negatieve getallen worden helemaal niet als priem of samengesteld beschouwd.

Hoe groot mag het bereik zijn dat ik kan opsommen?

Tot 1.000.000 — binnen dat bereik blijft de Zeef van Eratosthenes snel (de complexiteit O(n log log n) groeit heel langzaam) en blijft uw browser responsief.

Waarom hoeft proefdeling alleen tot de vierkantswortel te controleren?

Als een getal n een deler heeft die groter is dan √n, moet die gepaard gaan met een deler kleiner dan √n (aangezien hun product gelijk is aan n). Elk paar factoren heeft dus altijd minstens één lid op of onder de vierkantswortel — verder controleren is overbodig.

Waarom wordt voor het opsommen niet gewoon proefdeling gebruikt?

Dat zou kunnen, maar het zou veel trager zijn: elk getal in een bereik afzonderlijk testen tot aan zijn eigen vierkantswortel doet veel meer herhaald werk dan de zeef, die de veelvouden van elk priemgetal in één efficiënte doorgang over het hele bereik elimineert.

Zijn er oneindig veel priemgetallen?

Ja — Euclides gaf rond 300 v.Chr. een bewijs: neem aan dat er een eindige lijst van alle priemgetallen bestaat, vermenigvuldig ze allemaal en tel er 1 bij op; het resultaat is door geen enkel priemgetal op de lijst deelbaar, dus is het ofwel zelf een nieuw priemgetal, ofwel heeft het een priemfactor die niet op de lijst staat. Hoe dan ook, de lijst was onvolledig.

Reacties

Nog geen reacties — schrijf de eerste!

Vergelijkbare tools

Rekenmachine Gratis online rekenmachine met toetsenbordondersteuning: vier bewerkingen, percentages, haakjes en berekeningsgeschiedenis. Uitvoeren Percentage berekenen Bereken X% van een getal, hoeveel procent het ene getal van het andere is, en procentuele toe- of afname. Uitvoeren GGD & KGV Calculator Bereken de grootste gemene deler en het kleinste gemene veelvoud van twee of meer getallen, met getoonde stappen. Berekenen Combinatie- en permutatiecalculator Bereken C(n,r) combinaties, P(n,r) permutaties en n! faculteit met exacte resultaten. Berekenen