所謂素?cái)?shù)是指除了1和它本身以外，不能被任何整數(shù)整除的數(shù)，例如17就是素?cái)?shù)，因?yàn)樗荒鼙?~16的任一整數(shù)整除。因此判斷一個(gè)整數(shù)m是否是素?cái)?shù)，只需把m被2~m-1之間的每一個(gè)整數(shù)去除，如果都不能被整除，那么m就是一個(gè)素?cái)?shù)
另外判斷方法還可以簡(jiǎn)化。m不必唄2~m-1之間的每一個(gè)整數(shù)去除，只需被2~√m之間的每一個(gè)整數(shù)去除就可以了。如果m不能被2~√m間任一整數(shù)整除，m必定是素?cái)?shù)。例如判別17是是否為素?cái)?shù)，只需使17被2~4之間的每一個(gè)整數(shù)去除，由于都不能整除，可以判定17是素?cái)?shù)。（原因：因?yàn)槿绻鹠能被2~m-1之間任一整數(shù)整除，其二個(gè)因子必定有一個(gè)小于或等于√m，另一個(gè)大于或等于√m。例如16能被2,4,8整除。

判斷素?cái)?shù)O(sqrt(n))的算法哪有什么原理，就是窮舉。