數(shù)學(xué)知識(shí)
數(shù)學(xué)知識(shí)學(xué)習(xí)(持續(xù)更新)
Ⅰ 質(zhì)數(shù)
⒈ 試除法
?⑴ 判定素?cái)?shù)
時(shí)間復(fù)雜度：
⑵ 分解質(zhì)因數(shù)
時(shí)間復(fù)雜度： 與
?之間
⒉ 埃氏篩
原理：
將
~
排成一行，從第1個(gè)開始，在每個(gè)數(shù)上向后把這個(gè)數(shù)的倍數(shù)全部篩掉，這樣就可以只剩下質(zhì)數(shù)了。
時(shí)間復(fù)雜度：
附：一般，?會(huì)忽略不計(jì)，也就是說，時(shí)間復(fù)雜度近似
。但是，真正能做到
的算法是下一個(gè)算法——線性篩。
Code - 模板
Code - 用法
記
我們發(fā)現(xiàn)這里面似乎會(huì)對(duì)某些數(shù)標(biāo)記了很多次其為合數(shù)。有沒有什么辦法省掉無意義的步驟呢？請(qǐng)看下一個(gè)算法！
⒊ 線性篩法（埃氏篩優(yōu)化）
優(yōu)化方式：
我們?cè)谏弦粋€(gè)算法中提到埃氏篩會(huì)對(duì)某些數(shù)標(biāo)記了很多次其為合數(shù)，如果能讓每個(gè)合數(shù)都只被標(biāo)記一次，那么時(shí)間復(fù)雜度就可以降到 ?了。
時(shí)間復(fù)雜度：
Code - 模板
Code - 用法
分析
對(duì)于代碼
n 只會(huì)被最小的質(zhì)因子篩掉。
證明如下：
這里，我們分兩種情況來討論。
`i%primes[j]==0`，則 `primes[j]` 一定是 `i` 的最小質(zhì)因子，`primes[j]` 也一定是 `primes[j]*i` 的最小質(zhì)因子。
`i%primes[j]!=0`，則 `primes[j]` 一定小于 `i` 的所有質(zhì)因子，`primes[j]` 也一定是 `primes[j]*i` 的最小質(zhì)因子。
證畢!
Ⅱ 約數(shù)
您已讀完 10%，閱讀更多精彩內(nèi)容，請(qǐng)到以下鏈接訪問
1.?https://www.luogu.com.cn/blog/wangping/xn--48s96u
(推薦，時(shí)刻保持最新)
2.?https://blog.csdn.net/hello_wangping/article/details/122525289
(CSDN博客，隨后更新)
3.?https://www.cnblogs.com/wp-lvshu/p/15802232.html
(博客園，最后更新)
