 Then according to de Polignac's formula (actually due to Legendre)

where

But if only finitely many primes exist, then

(the numerator of the fraction would grow singly exponentially while by Stirling's approximation the denominator grows more quickly than singly exponentially),
contradicting the fact that for each "k" the numerator is greater than or equal to the denominator.Filip Saidak gave the following proof by construction, which does not use reductio ad absurdum or Euclid's Lemma (that if a prime "p" divides "ab" then it must divide "a" or "b").Since each natural number (> 1) has at least one prime factor, and two successive numbers "n" and ("n" + 1) have no factor in common, the product "n"("n" + 1) has more different prime factors than the number "n" itself.