亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

素數檢測算法

系統 2117 0

前言

今天做ACM的時候,遇到了素數的檢測,檢測一個范圍內的素數的時候,如果用最簡單的那種方法,超時嚴重,因此學習了一個新的素數檢測算法——素數篩選法,這里也是跟大家分享一下

素數

素數的定義

一個大于1的整數,如果不能被除1和它本身之外的其它正整數整除,則是素數(又稱質數)

合數的定義

一個大于1的整數,如果不是素數則是合數。其中能整除這個數的正整數叫做約數,不等于1也不等于合數本身的約數叫做非平凡約數。

注意:

1既不是素數也不是合數

檢測素數

所謂素數檢測,就是給定任意一個大于1的整數,判斷這個整數是否為素數。

因子檢測法

方法:就是從2到n-1一個個的拿來嘗試,看能否整除n,如果存在能夠整數n的(找到一個因子),則n不是素數,否則認為n是素數。實際,是不需要試探到n-1的,只要的n的二次方根即可,原因是:
設n = a * b,且a、b均為n非平凡約數,顯然a > n的二次方根和b > n的二次方根不可能同時成立,因為同時成立時 a * b就會大于n,所以如果n存在非平凡約數,至少有一個小于等于n的二次方根,因此只要遍歷到n的二次方根即可。

因子檢測的實現代碼如下(c):

      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;
}
    

測試結果:

時間復雜度:

很明顯,因子檢測算法的時間復雜度是0(n的二次方根),一般來說,這個時間復雜度已經很牛叉了,但是如果我要求n以內所有的素數集合,那時間復雜度瞬間就到了n * n的二次方根,這個對于n很大時是不可忍受的

素數篩選法

利用素數因子檢測法去超找n以內的所有素數,時間復雜度太高,不可忍受,因此這里介紹另外一種算法,素數篩選法,可以大大的節省時間,帶來的直接功效是九度acm關于素數檢測的題我瞬間ac,用素數因子檢測基本都是wa。

原理:

當i是素數的時候,則i的所有倍數必然是合數。如果i已經判斷不是素數了,那么找到i后面的質數來把這個質樹的倍數篩掉。

求20以內素數的篩選過程:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
第一步,因為所有的偶數和0,1必然不是質數,則將這些數的對應的value標記為flase,其余為true。
第二步:
i = 3,由于prime[3] = 1,則prime[6],prime[9],prime[12],prime[15],prime[18]均標記為0;
i = 4,由于prime[4] = 0,則continue,不做處理;
i = 5 > sqrt(20),算法結束

時間復雜度:

這個時間復雜度由于我的數學知識有限,也沒法把計算過程解釋出來,總之確實是很快,至于為什么i= 5就結束了,原因跟素數因子法里面的原理是一樣的,因為n的因子必然有一個是小于等于n的二次方根的。

素數篩選法實現代碼:

      void getPrimeArray(int *prime)
{
	int i, j;
	//初始化素數標識數組
	for(i = 0; i < max; i ++)
	{
		if((i == 2 || i % 2 != 0) && i != 1)
		{
			prime[i] = 1;
		} else
		{
			prime[i] = 0;
		}
	}
		
	//進行素數的篩選
	for(i = 2; i * i < max; i ++)
	{
		if(prime[i])
		{
			for(j = 2 * i; j < max; j += i)
			{
				prime[j] = 0;
			}
		}
	}

}
    

參考資料




素數檢測算法


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 2345成人高清毛片 | 五月婷婷丁香在线视频 | 免费看日韩欧美一级毛片 | 女人用粗大自熨喷水在线视频 | 亚洲视频1区 | 日本特级| 中文字幕日韩欧美一区二区三区 | 澳门久久精品 | 亚洲精品永久一区 | 五月天激情亚洲婷婷在线 | 日本中文字幕网站 | 久久综合综合久久狠狠狠97色 | 日本有色视频 | 99久久99视频 | 久久91亚洲精品中文字幕 | 成人黄性视频 | 九九久久国产 | 在线视频一二三区2021不卡 | 久久精品国产亚洲沈樵 | 天天曰天天爽 | 亚洲一区二区三区在线视频 | 亚洲精品国产五月色 | 成年性午夜免费视频网站不卡 | 久久精品国产福利 | 久揄揄鲁一二三四区高清在线 | 国产99视频精品免费视频免里 | 欧美一区欧美二区 | 国产亚洲精品yxsp | 青草青青在线视频 | 伊人精品视频 | 四虎伦理| 99热久久免费精品首页 | 香蕉久久网站 | 国产精品久久久免费视频 | 特大一级aaaaa毛片 | 国产色a在线观看 | 成年女人免费看 | 国产一区在线免费观看 | 国产激情一区二区三区 | 黄视频在线观看网站 | 欧美伦理一区二区三区 |