1、1数论简介数学学院：齐朋辉hutuQQ:9878932272本次讲座内容1.筛素数2.快速求幂3.费马小定理和欧拉定理4.解线性同余方程 (组 )3讲座前准备 数论是一门 专 门研究数字学科，包含了很多的东西，本次讲座仅限于一些 初步的知识，有兴趣的同学可以自己下来学习数论概论一书。51.筛素数1.素数的定义只能被自己 或 1整除的数。2.算术基本定理每个整数 n=2可唯一分解素数成n=p1*p2*p3.*pn.3.素数的用处. 分解整数. 状态哈希. 证明定理6如何判定一个数 n是否为素数 . 根据定义试除 2到 n-1中所有的数。 O(n) . 试除 2到 sqrt(n)的数， o(sqr
2、t(n) . 米勒 -拉宾素数判定 .o(k*logn)7如何进行大量的素数判定？（ 1=n=107） 算法一： O(m*n) 算法二： O(m*sqrt(n) 算法三： O(m*k*log(n) 如何做到 o(1)的判定？ 筛素数表8建立素数表的思路 对于一个素数 Pi，把 1n 内所有 pi的倍数都筛除掉，如果一个数 n，没有被前面的数筛除掉，则说明这个数为素数。9这样就得到一张 2-23的素数表10代码举例for(i=2;i=n;i+)if(!flagi)primet+=i;for(j=2;i*j=n;j+)flagi*j=1;11复杂度？ 对于 2n 每一个素数 pi 循环的次数为 n/pi 所以总的复杂度 n*(1/2+1/3+1/pi) 这个级数 不收敛 但是 n即使跑到 108 (1/2+1/3+1/pi)这个级数的和也 不 会超过 10 可以近似为常数 所以这个算法看成是近似线性的 有木有更快的方法呢？
