證明：假設素數是有限的，假設素數只有有限的n個，最大的一個素數是p，
設q為所有素數之積加上1，那麼，q=（ 2×3×5×…×p ）+1不是素數，
那麼，q可以被2、3、…、p中的數整除，
而q被這2、3、…、p中任意一個整除都會餘1，與之矛盾．
所以，素數是無限的．
另：
1.歐幾里得證法：
證：假設素數只有有限個，設為q1,q2,...qn，考慮p=q1q2...qn+1。顯然，p不能被q1,q2,...qn整除。故存在兩種情況：p為素數，或p有除q1,q2,...qn以外的其它素因子。無論何種情況，都說明素數不止有限個。假設錯誤，所以素數有無窮多個5.
2.
設p1,...,pn是n個兩兩不同的素數。再設Ar是其中任意取定的r個素數的乘積。證明：任一pj(1≤j≤n)都不能整除 p1...pn/Ar+Ar;
由此推出素數有無窮多個。
證：因為pj若不是Ar的因子，必然是p1...pn/Ar的因子；或者，pj若是Ar的因子，必然不是p1...pn/Ar的因子。因此，p1...pn/Ar+Ar或者是素數，或者除p1,...,pn之外有其它素因子。
無論何種情況，都說明素數不止有限個。假設錯誤，所以素數有無窮多個。
3.
設A1=2，An+1=An2-An+1(n≥1).再設n≠m.證明：若d|An,d>1,d不整除Am.由此推出素數有無窮多個。 證：當m>n時必有An|Am-1.方法同上。 綜上所述：以上證明可以分為兩類：
第一類：1.2.3.同樣用到了反證法，構造法。首先假設素數有有限個，透過構造數列，論證矛盾。
第二類：4.5.用到了構造法，直接證明法。透過構造數列，證明素數有無窮多個。
證明：假設素數是有限的，假設素數只有有限的n個，最大的一個素數是p，
設q為所有素數之積加上1，那麼，q=（ 2×3×5×…×p ）+1不是素數，
那麼，q可以被2、3、…、p中的數整除，
而q被這2、3、…、p中任意一個整除都會餘1，與之矛盾．
所以，素數是無限的．
另：
1.歐幾里得證法：
證：假設素數只有有限個，設為q1,q2,...qn，考慮p=q1q2...qn+1。顯然，p不能被q1,q2,...qn整除。故存在兩種情況：p為素數，或p有除q1,q2,...qn以外的其它素因子。無論何種情況，都說明素數不止有限個。假設錯誤，所以素數有無窮多個5.
2.
設p1,...,pn是n個兩兩不同的素數。再設Ar是其中任意取定的r個素數的乘積。證明：任一pj(1≤j≤n)都不能整除 p1...pn/Ar+Ar;
由此推出素數有無窮多個。
證：因為pj若不是Ar的因子，必然是p1...pn/Ar的因子；或者，pj若是Ar的因子，必然不是p1...pn/Ar的因子。因此，p1...pn/Ar+Ar或者是素數，或者除p1,...,pn之外有其它素因子。
無論何種情況，都說明素數不止有限個。假設錯誤，所以素數有無窮多個。
3.
設A1=2，An+1=An2-An+1(n≥1).再設n≠m.證明：若d|An,d>1,d不整除Am.由此推出素數有無窮多個。 證：當m>n時必有An|Am-1.方法同上。 綜上所述：以上證明可以分為兩類：
第一類：1.2.3.同樣用到了反證法，構造法。首先假設素數有有限個，透過構造數列，論證矛盾。
第二類：4.5.用到了構造法，直接證明法。透過構造數列，證明素數有無窮多個。