【OI之路】02数论算法-2素数

2.2.1 素数判断

1
2
3
4
5
6
7
8
#include<cmath>
bool Prime(int x)
{
if(x<2) return false;
if(x<4) return true;
  for(int i=2;i*i<=x;i++) if(x%i==0) return false;
  return true;
}

2.2.2 线性筛选素数

线性筛选素数,也就是O(n)
条件:积性函数,常见如素数函数、莫比乌斯函数、欧拉函数
精髓:每个合数都只被它的最小质因子筛出
注意,作为素数的循环j是在内部的
那么当i%prime[j]==0,意味着i中已经包含了prime[j]
那后面的数中,prime[j]一定会比prime[t]小
那么 至少 最小质因数不会是prime[t]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int MAXN=21000000;
int prime[1100000],pr;
bool v[MAXN];
void calcprime()
{
for(int i=2;i<=MAXN;i++)
{
if(v[i]==0) prime[++pr]=i;
if(pr==1000000) return;//满意而归
for(int j=1;j<=pr and i*prime[j]<=MAXN;j++)
{
if(i%prime[j]==0) break;
v[ i*prime[j] ]=1;
}
}
}

2.2.3 约数个数与和

对于数字G
$$G=p1^{a1}\times p2^{a2}\times p3^{a3}\times …\times pk^{ak}$$

$$约数个数=(a₁+1)(a₂+1)(a₃+1)…(ak+1)$$
$$和=
(p1^0+p1^1+…p1^{a1})
(p2^0+p2^1+…p2^{a2})
…(pk^0+pk^1+…pk^{ak})
$$

其实就是傻傻的乘法原理啦

2.2.4 其他知识

附赠几个有用的东西:

1.
通过$O(\sqrt n)$枚举出n的所有约数
推论: n的约数总数,上限$2 \sqrt n$

2.
通过$O(n log_2 n)$枚举d,更新其倍数得到1~n的所有约数
复杂度证明:调和级数
推论:1~n的所有约数个数,上限$n log_2 n$

3.
对于int范围内的x,其质因子数量<10
证明就是把最小那几个乘起来
然后指数总和<31

4.
素数分布数量
1~n大致上看作n/log n

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/ba6e.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%