初等数论-Base-1(筛法求素数，欧拉函数，欧几里得算法)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了初等数论-Base-1(筛法求素数，欧拉函数，欧几里得算法)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2517字，纯文字阅读大概需要4分钟。

内容图文

前言

初等数论在OI中应用的基础部分，同机房的AuSquare和zhou2003君早就写完了，一直划水偷懒的Hk-pls表示很方，这才开始了这篇博客.

$P.S.$可能会分部分发表。

筛法求素数

埃式筛素数

问题：求$[1,n]$中的所有素数

总体思路就是在$[2,n]$中每当我们找到一个新的素数，在把它加入我们的素数队列的同时我们把它的倍数全部打上标记（包括它自己），下一个没有被标记的数就是新的素数。

void find_prime(int n){
    memset(used,0,sizeof(used));cnt=0;
    for (int i=2;i<=n;++i){
        if (!used[i]) {prm[++cnt]=i;
            for (int j=1;(i*j)<=n;++j) used[i*j]=1;}
    }
}

这种方法简单粗暴，非常好写，且可以适用于很多种情况，但是，因为一个合数可能包含多个质因子这个算法就会不可避免地产生重复标记的情况，产生时间上的弊端。于是——

欧拉筛法

欧拉筛法是一种经典的线性筛法，顾名思义，欧拉筛法的时间复杂度为$O(n)$

同样地，欧拉筛法也是根据一个核心原理：每个合数必定可以被它的最小的质因子筛掉。

void euler(int N){
    memset(used,0,sizeof(used));cnt=0;
    for (int i=2;i<=n;++i){
        if (!used[i]) prm[++cnt]=i;
        for (int j=1;j<=cnt;++j) 
        {used[i*prm[j]]=prm[j];if (!(i%prm[j])) break;}
        /*这句话是重点：如果找到了i的最小质因子prm[j]我们就立马退出，
        因为剩下的没有标记的数将会在其他数的prm[j]倍中出现而被标记，
        例如：i=6在prm[j]=2之后退出，而它剩下未标记的18则会在i=9时被标记*/
    }
}

于是由于及时地跳出，欧拉筛法的时间优势得以产生。

例题：[USACO08DEC]拍头Patting Heads

欧拉函数

定义$[1,n]$中与$n$互素的数的个数为$\phi(n),$设$n$的素数表达式为$n=p_1^{a_1}\times p_2^{a_2}\times \cdots\times p_n^{a_n}$则：

$$\phi(n)=n\times(\frac{p_1-1}{p_1})\times(\frac{p_2-1}{p_2})\times\cdots\times(\frac{p_n-1}{p_n})=n\times\prod_{质数p|n}(\frac{p-1}{p})$$

证明：(来自李煜东的《算法竞赛进阶指南》)

利用容斥原理。

令$p,q$为$n$的不同的质因子，在$[1,n]$中，能整除$p$的有$\frac{n}{p}$个能整除$q$的有$\frac{n}{q}$个，但是可能会有$p,q$的倍数被重复减去的情况，所以我们需要在后面补上一个$\frac{n}{pq}$,则有：

$$n-\frac np-\frac nq+\frac{n}{pq}=n\cdot(1-\frac1p-\frac1q+\frac1{pq})=n\cdot(1-\frac1p)\cdot(1-\frac1q)$$

同理可得欧拉函数。

性质

1. 若$n$为素数，则有：$\phi(n)=n-1$

2. 欧拉函数是积性函数

欧几里得辗转相除法(Euclid's algorithm)

我相信这个式子应该是非常有名的

$$gcd(a,b)=gcd(b,a\space mod\space b)$$ 这里的$gcd(a,b)$指的是$a,b$的最大公因数。

令$gcd(a,b)=c,a\space mod\space b=d$,设$a=xc,b=yc,$
则$d=a-kb,k\in Z$
$d=a-kb=(x-ky)\cdot c$
故$c$一定也是$b,d$的因数，

若$(x-ky),y$不互素，则一定有$(x-ky)=e\cdot g,y=f\cdot g$，
则又有$x=ky+eg=kfg+eg=(kf+e)g$，
$a,b$可重新表示为$a=(kf+e)gc,b=fgc$,但此时$gcd(a,b)=cg,$与前面矛盾，
故$(x-ky),y$互素，则此时$gcd(b,a\space mod \space b)=gcd(a,b)=c$

即$gcd(a,b)=gcd(b,a\space mod\space b)$

证明完毕

内容总结

以上是互联网集市为您收集整理的初等数论-Base-1(筛法求素数，欧拉函数，欧几里得算法)全部内容，希望文章能够帮你解决初等数论-Base-1(筛法求素数，欧拉函数，欧几里得算法)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---