一个大于 1 的正整数，只能被 1 和自身整除，这样的正整数叫做：素数（质数）。否则，这样的正整数叫做合数。
如果 a 是一个大于 1 的正整数，且所有的不大于 √a 的素数都除不尽 a，则 a 是素数。
证明
先证明：如果所有不大于 √a 的素数都除不尽 a，则所有不大于 √a 的合数也除不尽 a。
反证法：如果有不大于 √a 的合数 m 可以除尽 a，则一定有小于 m 的素数 n 可以除尽 a（再次反正可以得出这个结论），n <= √a，与所有不大于 √a 的素数都除不尽 a 矛盾。
再证明：如果 a 是一个大于 1 的正整数，且所有的不大于 √a 的素数都除不尽 a，则 a 是素数。
反证法：如果 a 不是素数，a = bc，所有的不大于 √a 的素数都除不尽 a，所以 b > √a 且 c > √a，推出 bc > a，与 a = bc 矛盾。
原文：http://www.cnblogs.com/happyframework/p/3524646.html