畢達哥拉斯學派的人還觀察到一個現象，那就是有些數字沒有辦法表示成非平凡的矩形形狀（nontrivial rectangular shape），也就是說，沒有辦法用兩個邊都大于1的矩形來表示。這種數叫做素數（prime number），它們不能夠用比其更小且大于1的數之間的乘積來表示：
2, 3, 5, 7, 11, 13,…
（古希臘人所說的數都是指整數。）某些與素數有關的特征最早是由歐幾裡得觀察到的。盡管大家通常都會把他與幾何學聯系起來，但是《幾何原本》中有很多卷内容其實是在講數論。他所得到的其中一項結論就是下面這條定理：
定理3.1（《幾何原本》第7卷第32号命題） 任何數要麼是素數，要麼可以為某個素數所整除。
該定理的證明過程采用了一項技巧，它通過無窮遞降法（infinite descent）推導出一種不可能存在的情形。我們可以将此過程陳述如下：
證明 考慮A這個數。如果它是素數，那麼就得證。如果它是合數（composite，也就是非素數（nonprime）），那麼必定能夠為某個更小的數B所整除。如果B是素數，那麼得證（由于A可以為B所整除，而B又是素數，是以A就可以為該素數所整除）。如果B是合數，那麼必定能夠為某個更小的數C所整除，依此類推，我們最後必然能夠找到一個可以整除A的素數，假如找不到這樣的素數，那麼就會像歐幾裡得在證明同卷第31号命題時所說的那樣：得到一個無窮數列（infinite sequence of numbers），其中的每個數都可以整除A，而且後一個數要比前一個數小。然而這樣一種數列是不可能存在的。□
歐幾裡得的證明過程依賴于一項原則，那就是：由降序的自然數所形成的數列必定會終結。此原則與我們将要在第9章提到的自然數歸納公理（induction axiom of natural numbers）是等價的。
*
歐氏所得出的另一條結論，是說素數的個數無限多，有人認為這是最美的數學定理：
定理3.2（《幾何原本》第9卷第20号命題） 對于由素數所構成的任何一個數列{p1,…, pn}來說，總有一個素數p不在該數列中。
證明 考慮下面這個數：
其中的pi是指數列中的第i個素數。根據q的構造方式可知，它不可能為任何一個pi所整除。是以，q要麼本身就是素數，要麼則可以為不在數列中的其他某個素數所整除。如果是前一種情況，那麼q必然不在這個數列中；如果是後一種情況，那麼根據該數列的定義可知，能夠整除q的那個素數也不在這個數列中。是以，素數的個數是無限多的。
有一種廣為人知的素數搜尋方法，叫做埃拉托斯特尼篩法（Sieve of Eratosthenes）。埃拉托斯特尼是公元3世紀的希臘數學家，他的一項壯舉是相當精确地測量了地球的周長。這種素數搜尋算法的原理是将數字放在篩子裡進行篩選，把其中的非素數篩掉，使得素數能夠留在篩子裡面。執行算法時，要把所有的候選數字寫下來，然後将其中已知的非素數劃掉（這些數都是已經找到的那些素數的倍數），剩下來的數就是素數。今天在示範該算法的時候，會把從2到某個給定值之間的所有數字全部寫下來，但由于埃拉托斯特尼當時已經知道2之外的偶數都不是素數，是以他并沒有把這些數包含在内。
下面我們也按照埃氏的習慣，将偶數排除在外，也就是說，隻尋找大于2的那些素數。我們把從3開始直到給定值（該值記為m）之間的每一個候選數字，都放在篩子裡面。比方說，如果要尋找3到53（此時m = 53）之間的素數，那麼篩子裡面一開始會有這些數字：
反複執行這個篩選過程，直到把小于等于的倍數全都劃掉為止，其中的m是指候選數字裡面最大的那個數。
對于本例來說，由于m = 53，是以隻需要執行到7的倍數這一輪就可以停止了。還沒有劃掉的數字全都是素數：
在用程式代碼實作該算法之前，我們先來觀察它的幾項特征。在篩選過程進行到一半的時候（比方說，在正要劃掉5的倍數時），我們給候選數字添加一些資訊，也就是把每個數字在數列中的序号（index）或者說位置标在該數上方。
大家可以看到，在考慮5的倍數時，我們所劃掉的25和35這兩個數字，其距離恰好是5，這個間隔距離就叫做步長（step size）。如果改用另外一種說法，那就是：在某一輪篩選過程中所劃掉的這兩個候選數字，其序号之間的差距等于本輪開頭所用的那個素數。此外，由于候選數列中隻包含奇數，是以，劃掉的這兩個數值其數量差距是序号差距的2倍。是以我們可以說，某一輪篩選過程中所劃掉的這兩個候選數字（例如25和35）其數量差距是步長的2倍，或者說是本輪開頭所用的那個素數的2倍。剛才我們是以5為例來進行說明的，對于其他數字來說，這個規律同樣成立。
最後，我們還觀察到另外一個現象，那就是：每一輪篩選時，第一個劃掉的數字總是目前這一輪所用的那個素數的平方。例如在考慮5的倍數時，第一個劃掉的數字必然是25，因為盡管兩者之間還有一些數字也是5的倍數，但我們早前在考慮其他素數時，已經把那些數劃掉了。