素数

• • • 定义

    • 性质

    • 哥德巴赫猜想

    • 贝特朗假设

    • 素数定理

    • 算术基本定理

    • 勒让德定理

    • 欧拉函数

    • 积性函数

    • 筛法

      • 埃拉托斯特尼筛法 $O(nloglogn)O(nloglogn)$
      • 欧拉筛/线性筛 $O(n)O(n)$

    • 素性测试

      • 二次探测定理
      • 米勒-拉宾算法

定义

一个大于1的自然数，除了1 和它自身外，不能整除其他自然数的数

性质

• 素数有无穷多个
• 存在任意长的连续数，其中所有数都是合数(相邻素数之间的间隔任意大)
• 随着$nn$的增大素数越来越稀疏

哥德巴赫猜想

任意大于2的正偶数都可以写成两个素数的和 一个充分大偶数必定可以写成一个素数加上最多由2个质因子所组合的合成数，简称为(1+2)

贝特朗假设

对任意 $n\ge 1n\backslash geq1$ , $nn$ 到 $2n2n$ 之间(不包括n)至少存在一个质数。

推论：$2^{n}2^n$ 之内至少存在n个质数

素数定理

设$n\ge 2n\backslash geq2$，以 $\pi (x)\backslash pi(x)$ 表示不超过 $xx$ 的素数的个数，当 $n\to \mathrm{\infty }n\; \backslash to\; \backslash infty$ 时，

推论：从不大于 $nn$ 的自然数随机选一个，它是素数的概率大约是 $\frac{1}{\mathrm{l}\mathrm{n}\mathrm{n}}\backslash frac\{1\}\; \{\backslash rm\; ln\; n\}$

算术基本定理

任何一个大于1的正整数都能唯一分解为有限个质数的乘积，可写作：

其中 $c_{i}c\_i$ 都是正整数，$p_{i}p\_i$都是质数，且满足。 推论：$NN$的正约束的集合可写作：

$NN$ 的正约数个数为

$NN$ 的正约数的和为：

勒让德定理

$N!N!$中质因子 $pp$ 的个数为：

欧拉函数

1~$N\backslash small\; N$ 中与 $NN$ 互质的数的个数被称为欧拉函数，记为 $\phi (N)\backslash varphi(N)$。

在算术基本定理中, $N=p_1^{c_1}{p}_2^{c_2}\cdots p_m^{c_m}\backslash small\; N=p\_1^\{c\_1\}p\_2^\{c\_2\}\backslash cdots\; p\_m^\{c\_m\}$, 则：

原理：由容斥原理可得，设 $p,qp,q$ 是 $NN$ 的质因子，1~$N\backslash small\; N$ 中共有 $\frac{N}{p}\backslash frac\{N\}\{p\}$ 个 $pp$ 的倍数，$\frac{N}{q}\backslash frac\{N\}\{q\}$ 个 $qq$ 的倍数,同时有$\frac{N}{pq}\backslash frac\{N\}\{pq\}$ 个 $pqpq$ 的倍数，因此剩下数的个数有：

性质

1. $pp$ 为素数 ，则 $\phi (p)=p-1,\phi (p^k)=(p-1)p^{k-1}\backslash varphi(p)=p-1,\; \backslash varphi(p^k)=(p-1)p^\{k-1\}$
2. $\mathrm{\forall }n>1,1\backslash forall\; n>1,1$~$nn$ 中与 $nn$ 互素的数的和为 $\frac{n\ast \phi (n)}{2}\backslash Large\backslash frac\{n*\backslash varphi(n)\}\{2\}$
3. 若 $a,ba,b$ 互素，则 $\phi (ab)=\phi (a)\phi (b)\backslash varphi\; (ab)=\backslash varphi\; (a)\backslash varphi\; (b)$
4. $pp$ 为素数，若 $p\mid np\backslash mid\; n$ 且 $p^2\mid np^2\backslash mid\; n$, 则 $\phi (n)=\phi (\frac{n}{p})\ast p\backslash varphi(n)=\backslash varphi(\backslash frac\{n\}\{p\})*p$
5. $pp$ 为素数，若 $p\mid np\backslash mid\; n$ 但 $p^2\nmid np^2\backslash nmid\; n$, 则 $\phi (n)=\phi (\frac{n}{p})\ast (p-1)\backslash varphi(n)=\backslash varphi(\backslash frac\{n\}\{p\})*(p-1)$
6. ${\sum }_{d\mid n}\phi (d)=n\backslash sum\_\{d\backslash mid\; n\}\backslash varphi(d)=n$

积性函数

如果当 $a,ba,b$ 互素时，有 $f(ab)=f(a)\ast f(b)f(ab)=f(a)*f(b)$，那么称函数 $ff$ 为积性函数。

性质

若是 $ff$ 积性函数，且在算术基本定理中 $n={\prod }_{i=1}^m{p}_i^{c_i}n=\backslash prod\_\{i=1\}^m\; p\_i^\{c\_i\}$ ，则 $f(n)={\prod }_{i=1}^{m}f(p_i^{c_i})f(n)=\backslash prod\_\{i=1\}^m\; f(p\_i^\{c\_i\})$

筛法

埃拉托斯特尼筛法 $O(nloglogn)O(nloglogn)$

void primes(ll n){
    for(int i=2;i<=n;i++){
        if(v[i])continue;//如果被筛过
        cout<<i<<endl;//剩下的为素数
        for(int j=i;j*i<=n;j++){//筛掉其倍数
            v[i*j]=1;
        }
    }
}

欧拉筛/线性筛 $O(n)O(n)$

确保每个合数只会被其最小质因子筛过

void primes(ll n){
    for(int i=2;i<=n;i++){
        if(v[i]==0){v[i]=i;prime[++cnt]=i;}
        for(int j=1;j<=cnt;j++){
            //prime[j]应为比i筛过的最小质因子小
            if(prime[j]>v[i]||i*prime[j]>n)break;
            v[i*prime[j]]=prime[j];
        }
    }
}

素性测试

二次探测定理

若 $pp$ 为素数, $a^2\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)a^2\backslash equiv1\backslash pmod\; p$ ，那么 $a\equiv \pm 1(\mathrm{m}\mathrm{o}\mathrm{d}p)a\backslash equiv\; \backslash pm1\backslash pmod\; p$

米勒-拉宾算法

利用费马小定理对数进行素性测试，并通过二次探测定理检验，具有极高正确概率的算法。判断一个数 $pp$ 是否为素数,将其 $p-1p-1$ 分解成 $t\times 2^{k}t\backslash times\; 2^k$, 先对 $a^t(\mathrm{m}\mathrm{o}\mathrm{d}p)a^t\backslash pmod\; p$ 进行费马检验，再进行最多 $tt$ 次平方操作，每次根据二次探测定理检验

bool miller_rabin(ll p) {
    if(p<3||p%2==0) return p==2;
    int Test[]={2,3,5,7,11,13,17,19};
    int t = p - 1, k = 0;
    while(!(t & 1)) k++, t >>= 1;
    for(int i = 0; i < 8; i++) {
        if(p == Test[i]) return 1;
        ll a = quick_power(Test[i], t, p), nxt = a;
        //ll x=rand()%(p-2)+2,a=quick_power(x,t,p);
        for(int j = 1; j <= k; j++) {
            nxt = (a * a) % p;
            if(nxt == 1 && a != 1 && a != p - 1) return 0;
            a = nxt;
        }
        if(a != 1) return 0;
    }
    return 1;
}