說明判斷質數的方式?

Proposition 1.4.6 若 n > 1 是一整數且對任意小於等於 √n的質數 p 皆不能整除 n, 則 n 為一質數.
証 明. 因為我們無法直接證明 n 會是質數, 所以需用反證法. 假設 n 不是質數, 依定義知存在 a, b∈Z 滿足 1 < ab < n 且 n = ab. 由此我們可以確定 a<=√n, 否則若 a >√n 會造成 ab > (√n)^2 = n 而與 n = ab 不合.
而由 Lemma 1.4.4 知存在質數 p 使得 p| a. 既然 p| a 我們得 p<=a<=√n且 p| n. 此與假設所有小於等於√n 的質數皆不整除 n 不符, 故知 n 為質數. Proposition 1.4.6 所提判別質數方法稱為篩法 (sieve method). 它可以幫助我們篩得哪些數是質數. http://math.ntnu.edu.tw/~li/ent-html/node6.html

任一正整數n必存在至少一因數小於等於根號n