数学知识学习(持续更新)

Ⅰ 质数

⒈ 试除法

 ⑴ 判定素数

时间复杂度：

⑵ 分解质因数

时间复杂度： 与  之间

⒉ 埃氏筛

原理：

将 ~ 排成一行，从第1个开始，在每个数上向后把这个数的倍数全部筛掉，这样就可以只剩下质数了。

时间复杂度：

附：一般， 会忽略不计，也就是说，时间复杂度近似 。但是，真正能做到 的算法是下一个算法——线性筛。

Code - 模板

Code - 用法

记

我们发现这里面似乎会对某些数标记了很多次其为合数。有没有什么办法省掉无意义的步骤呢？请看下一个算法！

⒊ 线性筛法（埃氏筛优化）

优化方式：

我们在上一个算法中提到埃氏筛会对某些数标记了很多次其为合数，如果能让每个合数都只被标记一次，那么时间复杂度就可以降到  了。

时间复杂度：

Code - 模板

Code - 用法

分析

对于代码

n 只会被最小的质因子筛掉。

证明如下：

这里，我们分两种情况来讨论。

1. `i%primes[j]==0`，则 `primes[j]` 一定是 `i` 的最小质因子，`primes[j]` 也一定是 `primes[j]*i` 的最小质因子。

2. `i%primes[j]!=0`，则 `primes[j]` 一定小于 `i` 的所有质因子，`primes[j]` 也一定是 `primes[j]*i` 的最小质因子。

证毕!

Ⅱ 约数

您已读完 10%，阅读更多精彩内容，请到以下链接访问

1. https://www.luogu.com.cn/blog/wangping/xn--48s96u

(推荐，时刻保持最新)

2. https://blog.csdn.net/hello_wangping/article/details/122525289

(CSDN博客，随后更新)

3. https://www.cnblogs.com/wp-lvshu/p/15802232.html

(博客园，最后更新)