數(shù)學(xué)知識(shí)-質(zhì)數(shù)

數(shù)學(xué)知識(shí)-數(shù)論-質(zhì)數(shù)河南省實(shí)驗(yàn)中學(xué)信息組質(zhì)數(shù)質(zhì)數(shù)的判定

數(shù)字約數(shù)3612346912183637137質(zhì)數(shù)的篩選

埃氏篩埃氏篩(Eratosthenes篩法)思想：任意正整數(shù)x的倍數(shù)2*x,3*x,?都不是質(zhì)數(shù)。從2開(kāi)始遍歷每一個(gè)數(shù)x，如果它是質(zhì)數(shù)，把它的倍數(shù)2x,3x,?,?n?x??x標(biāo)記為合數(shù)。當(dāng)掃描到一個(gè)數(shù)x時(shí)，若它尚未標(biāo)記，則它不能被2~x?1之間的任何數(shù)整除，該數(shù)就是質(zhì)數(shù)。埃氏篩的時(shí)間復(fù)雜度：例如找出100內(nèi)所有素?cái)?shù)，如下圖：首先2的倍數(shù)篩去3的倍數(shù)篩去12又被篩了一次，某些數(shù)字有重復(fù)篩的問(wèn)題。5的倍數(shù)篩去7的倍數(shù)篩去還需要繼續(xù)嗎？11*11=121超過(guò)了100歐氏篩歐氏篩(歐拉篩法/線性篩法)

經(jīng)過(guò)優(yōu)化后的埃氏篩仍會(huì)重復(fù)篩除合數(shù)。例如，12既會(huì)被2篩也會(huì)被3篩，這就出現(xiàn)了重復(fù)篩選；再例如，30被2、3、5各篩一次。問(wèn)題：是否存在線性篩法，讓每個(gè)合數(shù)只篩一次？歐拉篩法就是一種線性篩法。

考慮：有什么辦法讓每個(gè)合數(shù)只被篩一次？我們知道合數(shù)可以質(zhì)因式分解，最小質(zhì)因子是唯一的，我們能不能讓每個(gè)合數(shù)被它的最小質(zhì)因子篩掉？以45以內(nèi)的所有數(shù)為例：質(zhì)數(shù)：2、3、5、7、11、13、17、19、23、29、31、37、41、43合數(shù)：4、6、8、9、10、12、14、15、16、18、20、21、22、24、25、26、27、28、30、32、33、34、35、36、38、39、40、42、44、45將所有合數(shù)分解成最小質(zhì)因子做被乘數(shù)的形式，確保被乘數(shù)小于等于乘數(shù)。被乘數(shù)相同的寫一行，如下：2*2、2*3、2*4、2*5、2*6、2*7、2*8、2*9、2*10、2*11、2*12、2*13、2*14、2*15、2*16、2*17、2*18、2*19、2*20、2*21、2*223*3、3*5、3*7、3*9、3*11、3*13、3*155*5、5*7、5*9問(wèn)題：怎樣才能按照上面的順序進(jìn)行篩？換個(gè)順序?qū)?，乘?shù)相同的寫一行，被乘數(shù)小于等于乘數(shù)2*22*3、3*32*42*5、3*5、5*52*62*7、3*7、5*72*82*9、3*92*102*11、3*112*122*13、3*132*142*15、3*152*162*17……2*22當(dāng)乘數(shù)是被乘數(shù)的倍數(shù)時(shí)，停止篩除。3*4不會(huì)出現(xiàn)，4中必有2這個(gè)因子，而2<3，會(huì)在2*6時(shí)篩除思路：以乘數(shù)作為循環(huán)變量i，如果i沒(méi)有被標(biāo)記，i記入質(zhì)數(shù)表，質(zhì)數(shù)表中現(xiàn)有質(zhì)數(shù)與i乘積的數(shù)則為合數(shù)，將其標(biāo)記篩掉，注意當(dāng)乘數(shù)是被乘數(shù)的倍數(shù)時(shí)停止i的處理，開(kāi)始篩i+1為什么循環(huán)到n，而不是n/i?歐氏篩還有另外一種寫法設(shè)數(shù)組v記錄每個(gè)數(shù)的最小質(zhì)因子，即該數(shù)被哪個(gè)數(shù)篩，我們按照如下步驟維護(hù)v:

依次考慮2~N之間的每一個(gè)數(shù)i；如果v[i]=0，說(shuō)明i未被篩過(guò)，即為質(zhì)數(shù)，把它存下來(lái)，并令v[i]=i；如果v[i]≠0，掃描不大于v[i]的每個(gè)質(zhì)數(shù)p，令v[i*p]=p。因?yàn)閜≤v[i]，而p是從最小的質(zhì)數(shù)開(kāi)始掃描的，所以p就是合數(shù)i?p的最小質(zhì)因子。因?yàn)槊總€(gè)合數(shù)i?p只會(huì)被他的最小質(zhì)因子p篩一次，時(shí)間復(fù)雜度為O(N)。算術(shù)基本定理質(zhì)因數(shù)分解質(zhì)因數(shù)分解

質(zhì)因數(shù)分解【例】PRIMEDISTANCE(COGS3478)給定兩個(gè)整數(shù)L,R(1≤L≤R≤231,R?L≤106)，求閉區(qū)間[L,R]內(nèi)相鄰兩個(gè)質(zhì)數(shù)的差的最大是多少，輸出這兩個(gè)質(zhì)數(shù)。(輸入數(shù)據(jù)有多組)

輸入格式：多行，每行兩個(gè)整數(shù)L,R。輸出格式：多行，每行連個(gè)整數(shù)表示差最大的兩個(gè)質(zhì)數(shù)(小數(shù)在前，大數(shù)在后)，如果有多組解輸出較小的，如果沒(méi)有解輸出“noadjacentprimes”。輸入樣例：輸出樣例：2177111417noadjacentprimes樣例解釋：2~17中的質(zhì)數(shù)有2、3、5、7、11、13、