1、长沙市雅礼中学 朱全民数论知识点 素数与合数 质因素的分解 最大公约数与最小公倍数 整除与同余 同余方程与同余方程组 欧几里德算法、扩展欧几里德算法、中国剩余定理 欧拉定理与费马小定理思考题 1： 素数密度问题描述给定区间 L, R(L = R = 2147483647， R-L = 1000000)，请计算区间中素数的个数。输入数据两个数 L和 R。输出数据一行，区间中素数的个数。梅森素数 把形如 (2p-1)形式的素数称为梅森素数， p是素数。 1, 231-1之间的梅森素数有： 22-1, 23-1, 25-1, 27-1, 213-1, 217-1, 219-1, 231-1 梅森素数
2、的一个性质：一个正整数 n的所有约数和是 2的幂当且仅当 n能够被分解为若干个不同的梅森素数之积。思考题 2:fibonacci数列 已知 f1=1,f2=1 fn=fn-1+fn-2 给出 n,如何快速求 fibonacci数列的 fn分析 普通的算法求 Fn的时间复杂度为 O(n)，当然如果要求求出所有的 Fn，这种已经是最优的了，但是如果只求某一个 Fn，可以改进F(n)=(1/5)*(1+5)/2n - (1-5)/2n 唯一因子分解唯一质因子分解定理：合数 a仅能以一种方式，写成如下的乘积形式：a=p1e1p2e2 prer其中 pi为素数， p1p2 pr，且 ei为正整数关于约数的公式n！的素因子分解式整数分解方法 大整数分解现在任然是个世界级的难题 ! 而对于大整数的分解有很多种算法，性能上各有优异，比如大整数分解的 Fermat方法， Pollard rho方法，试除法，以及椭圆曲线法，连分数法，二次筛选法，数域分析法等等。这里，主要讲解其中两种算法的原理和操作。
