Het bewijs dat er oneindig veel priemgetallen bestaan kan iedereen bij Euclides (300vC) nalezen. In 2019 verscheen op het internet (hier, getekend Adrian W. Dudek) een nieuw, doodeenvoudig bewijs, dat bovendien een soort "constructief" karakter heeft dat bij Euclides ontbreekt.
Elk natuurlijk getal (vanaf 2) is een product van priemgetallen. Zo is 7 een priemgetal, en 12=2x2x3; we zeggen: 7 heeft één priemfactor, namelijk zichzelf, en 12 heeft er twee, namelijk 2 en 3. Het is een eenvoudige vaststelling dat de natuurlijke getallen n en n+1 geen gemeenschappelijke priemfactoren hebben. (Inderdaad, als n deelbaar is door p, dan is n+1 een p-voud+1.) De priemfactoren van het product n(n+1) kunnen dus verdeeld worden in twee disjuncte verzamelingen: de priemfactoren van n en (bijkomend) de priemfactoren van n+1. Bijgevolg: n(n+1) heeft méér priemfactoren dan n.
Als we beginnen bij het eerste priemgetal, en dit vermenigvuldigen met het getal dat 1 groter is, dan vinden we een nieuw getal dat minstens 2 priemfactoren heeft. Herhalen we dit, telkens het verkregen getal vermenigvuldigend met het getal dat 1 groter is, dan vinden we een oneindige rij van getallen die telkens minstens één priemfactor méér hebben dat het vorige getal. (Bij elke stap is de toename van het aantal priemfactoren minstens 1, maar niet steeds gelijk aan 1, zie hieronder.)
Deze werkwijze, voldoende ver doorgezet, levert een getal op met een aantal priemfactoren groter dan of gelijk aan een willekeurig vooraf gegeven getal.
Het klassieke bewijs van Euclides berust op de eigenschap: telt men 1 op bij een product van verschillende priemgetallen, dan heeft het nieuwe getal minstens 1 priemfactor die in het product niet voorkwam. (Inderdaad, is p een van de gebruikte priemgetallen, dan is p geen deler van het nieuwe getal, dat immers een p-voud+1 is. Een priemfactor van het nieuwe getal verschilt dus van alle gebruikte priemgetallen.) Hieruit volgt eveneens dat de rij van de priemgetallen oneindig is. Om in deze rij te vorderen moet men wel een steeds groeiende verzameling van priemgetallen construeren, m.a.w., eigenlijk moet men de verkregen getallen telkens in priemfactoren ontbinden. Bij het bewijs uit 2019 moet men de priemgetallen zelf niet kennen. Op het zwarte bord hierboven staan de getallen ontbonden in priemfactoren, maar dat is enkel om het aantal priemfactoren te tonen; nodig is het niet.
