質數有多少個？

10 之內的質數有 4 個：2, 3, 5, 7。

100 之內的質數有 23 個，100 之上當然還有很多質數，究竟質數有多少個？最大的質數是甚麼？

古希臘數學家歐幾里德用一個簡潔而漂亮的反證法，證明了質數有無限多個。

他首先假設質數的數量是有限的，姑且說這批質數就是 p1, p2, p3, ..., pn，其餘數字都是合成數，歐幾里德跟着計算以下數字：

N = p1 x p2 x p3 x ...... x pn + 1

這個 N 比任何一個已知的質數都大，所以一定是一個合成數，即是說 N 一定可以被至少一個質數整除，但是 N 不論除以 p1, p2, ……. 乃至 pn，都得到餘數 1，換句話說，N 不能被任何一個已知的質數整除。N 既不能是質數（因為它比所有已知的質數都大），也不能是合成數（因為沒有一個質數能整除它），這時唯一的解釋，是開首的假設，即「質數的數量是有限的」有錯，結論是質數是無限的。