今天做ACM的時(shí)候，遇到了素?cái)?shù)的檢測(cè)，檢測(cè)一個(gè)范圍內(nèi)的素?cái)?shù)的時(shí)候，如果用最簡(jiǎn)單的那種方法，超時(shí)嚴(yán)重，因此學(xué)習(xí)了一個(gè)新的素?cái)?shù)檢測(cè)算法——素?cái)?shù)篩選法，這里也是跟大家分享一下

一個(gè)大于1的整數(shù)，如果不能被除1和它本身之外的其它正整數(shù)整除，則是素?cái)?shù)（又稱(chēng)質(zhì)數(shù)）

一個(gè)大于1的整數(shù)，如果不是素?cái)?shù)則是合數(shù)。其中能整除這個(gè)數(shù)的正整數(shù)叫做約數(shù)，不等于1也不等于合數(shù)本身的約數(shù)叫做非平凡約數(shù)。

1既不是素?cái)?shù)也不是合數(shù)

所謂素?cái)?shù)檢測(cè)，就是給定任意一個(gè)大于1的整數(shù)，判斷這個(gè)整數(shù)是否為素?cái)?shù)。

方法：就是從2到ｎ-1一個(gè)個(gè)的拿來(lái)嘗試，看能否整除ｎ，如果存在能夠整數(shù)ｎ的（找到一個(gè)因子），則ｎ不是素?cái)?shù)，否則認(rèn)為ｎ是素?cái)?shù)。實(shí)際，是不需要試探到ｎ-1的，只要的ｎ的二次方根即可，原因是：

設(shè)n = a * b,且a、b均為n非平凡約數(shù)，顯然a > n的二次方根和b > n的二次方根不可能同時(shí)成立，因?yàn)橥瑫r(shí)成立時(shí) a * b就會(huì)大于n，所以如果n存在非平凡約數(shù)，至少有一個(gè)小于等于n的二次方根，因此只要遍歷到ｎ的二次方根即可。

      int isPrime(int n)
{
	int i, flag;
	flag = (n <= 1)? 0 : 1;
	
	for(i = 2; i <= sqrt(n); i ++)
	{
		if(n % i == 0)
		{
			flag = 0;
			break;
		}
	}
	return flag;
}
    

很明顯，因子檢測(cè)算法的時(shí)間復(fù)雜度是0（ｎ的二次方根）,一般來(lái)說(shuō)，這個(gè)時(shí)間復(fù)雜度已經(jīng)很牛叉了，但是如果我要求ｎ以?xún)?nèi)所有的素?cái)?shù)集合，那時(shí)間復(fù)雜度瞬間就到了n * n的二次方根，這個(gè)對(duì)于ｎ很大時(shí)是不可忍受的

利用素?cái)?shù)因子檢測(cè)法去超找ｎ以?xún)?nèi)的所有素?cái)?shù)，時(shí)間復(fù)雜度太高，不可忍受，因此這里介紹另外一種算法，素?cái)?shù)篩選法，可以大大的節(jié)省時(shí)間，帶來(lái)的直接功效是九度ａｃｍ關(guān)于素?cái)?shù)檢測(cè)的題我瞬間ａｃ，用素?cái)?shù)因子檢測(cè)基本都是ｗａ。

當(dāng)i是素?cái)?shù)的時(shí)候，則ｉ的所有倍數(shù)必然是合數(shù)。如果ｉ已經(jīng)判斷不是素?cái)?shù)了，那么找到ｉ后面的質(zhì)數(shù)來(lái)把這個(gè)質(zhì)樹(shù)的倍數(shù)篩掉。

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

第一步，因?yàn)樗械呐紨?shù)和0,1必然不是質(zhì)數(shù)，則將這些數(shù)的對(duì)應(yīng)的value標(biāo)記為flase，其余為true。

第二步：

i = 3,由于prime[3] = 1,則prime[6],prime[9],prime[12],prime[15],prime[18]均標(biāo)記為0;

i = 4,由于prime[4] = 0,則continue，不做處理;

i = 5 > sqrt(20),算法結(jié)束

這個(gè)時(shí)間復(fù)雜度由于我的數(shù)學(xué)知識(shí)有限，也沒(méi)法把計(jì)算過(guò)程解釋出來(lái)，總之確實(shí)是很快，至于為什么ｉ= 5就結(jié)束了，原因跟素?cái)?shù)因子法里面的原理是一樣的，因?yàn)椋畹囊蜃颖厝挥幸粋€(gè)是小于等于n的二次方根的。

      void getPrimeArray(int *prime)
{
	int i, j;
	//初始化素?cái)?shù)標(biāo)識(shí)數(shù)組
	for(i = 0; i < max; i ++)
	{
		if((i == 2 || i % 2 != 0) && i != 1)
		{
			prime[i] = 1;
		} else
		{
			prime[i] = 0;
		}
	}
		
	//進(jìn)行素?cái)?shù)的篩選
	for(i = 2; i * i < max; i ++)
	{
		if(prime[i])
		{
			for(j = 2 * i; j < max; j += i)
			{
				prime[j] = 0;
			}
		}
	}

}
    

參考資料

張洋的博客——http://www.codinglabs.org/html/prime-test.html 我很崇拜的一個(gè)技術(shù)牛人