素?cái)?shù)的定義
素?cái)?shù)：又稱質(zhì)數(shù)高职。是大于1自然數(shù)中的除了自身和1以外不能別其他數(shù)整除的數(shù)字烈和。
第一種方法
利用這個(gè)素?cái)?shù)的定義，我們可以得出第一種判斷素?cái)?shù)的方法：
int isPrime1(int n)
{
int i = 0;
//2是素?cái)?shù)
if(n <= 3)
return n > 1;
//當(dāng)n不能被除了1和n自身整除的數(shù)外的數(shù)是素?cái)?shù)
for(i = 2; i < n; i ++)
{
if(n % i == 0)
return 0;
}
return 1;
}
這個(gè)方法是最簡(jiǎn)單的判斷方法，它使用一個(gè)for循環(huán)來讓n一次次的除以小于n的每個(gè)數(shù)执解，如果除盡了的話，就不滿足素?cái)?shù)的定義纲酗。
但是這個(gè)方法也是計(jì)算量最大的衰腌。它總共會(huì)計(jì)算n-2次。
第二種方法
第二種方式是：如果 n 能夠被 2 ~ 之間的數(shù)整除就不是素?cái)?shù)（合數(shù)）觅赊，反之為素?cái)?shù)右蕊。
所以，根據(jù)這個(gè)性質(zhì)我們可以減少判斷的次數(shù)來節(jié)約運(yùn)算時(shí)間吮螺。
int isPrime2(int n)
{
int i = 0;
if(n <= 3)
return n > 1;
//講判斷條件改為 i <= sqrt(n)尤泽，即對(duì)n開平方
for(i = 2; i <= sqrt(n); i ++)
{
if(n % i == 0)
return 0;
}
return 1;
}
這個(gè)方法比上一個(gè)方法減少了很多的時(shí)間。所以使用這種方法的時(shí)候會(huì)更能提高程序的效率规脸。
有人可能會(huì)問坯约，這里為什么是 ？
因?yàn)橐粋€(gè)數(shù) N 的的因數(shù)可以分為兩部分莫鸭，一部分是小于 的闹丐，另一部分是大于
的。而小于的那部分和大于的一一對(duì)應(yīng)被因。所以只需要判斷 2 ~
即可卿拴。
