1、CUGB ACM/ICPC GROUPSPEAKER: Zhou Xing2011.4.13数论小站CUGB ACM/ICPC GROUP 整除 :如果 a和 b是整数， a0 ，若有整数 c使 b ac，就说 a整除 b。在 a整除 b时，记 a是 b的一个因子， b是 a的倍数。用符号 ab 表示 a整除 b， a不能整除 b记为 a b 。 整除基本性质有：（ 1）若 ab ， ac ，则 a （ b c）（ 2）若 ab ，则对所有整数 c， abc（ 3）若 ab ， bc ，则 ac （传递性）数论基本知识CUGB ACM/ICPC GROUP 素数（ prime）和合数（ com
2、pound），如果一个整数 p只有 1和 p两个因子，则 p为素数，不为素数的其它数为合数。 如果 n为合数，则 n必有一个小于或等于 n的平方根的数因子。 给出一个数 n，如何判断它是不是素数？ 朴素的判别法 从 2开始试除小于 n的所有自然数，时间复杂度为 O(n). 如果 a是 n的因子，那么 n/a也是 n的因子，所以如果n有一个大于 1的真因子，则它必有一个不大于 n1/2的因子，时间复杂度 O(n1/2)。数轮基本知识CUGB ACM/ICPC GROUP 算术基本定理：每个正整数都可以唯一地表示成素数的乘积。其中素数因子从小到大依次出现。 最大公约数 gcd(a, b) 最小公倍
3、数 lcm(a, b) ab gcd(a, b)lcm(a, b) 如果 gcd(a, b)=1，则 a与 b互素。数论基本知识CUGB ACM/ICPC GROUP 最一般的求解 n以内素数的算法。复杂度是o(n*sqrt(n)，适合 n很小num = 0; for(i=2; isqrt(i) ) primenum+ = i; 素数算法CUGB ACM/ICPC GROUP 如何求出 1 n中的所有素数？ 筛法 1：Eraosthenes（爱拉托斯尼筛法）筛法：每次求出一个新的素数，就把 n以内的它的所有倍数都筛去。经典的 Eraosthenes筛法（核心代码）：for (int i = 2
4、; i * i N; i+)if (tagi) continue;for (int j = i; i * j N; j+)tagi*j = 1;for (int i = 2; i N; i+)if (!tagi)primetol+ = i;素数求法CUGB ACM/ICPC GROUP 筛法 2： 一种线性筛素数的方法（复杂度是 O(n)）：void get_prime() int cnt = 0;for (int i = 2; i N; i+)if (!tagi) pcnt+ = i;for (int j = 0; j cnt j+)tagi*pj = 1;if (i % pj = 0)br
5、eak;/可以用均摊分析的方法来分析算法的复杂度 ,由于每 个合数都唯一的被它的最小素因子筛一次，而每个合 数的最小素因子都是唯一的，总复杂度是 O(n) 素数求法CUGB ACM/ICPC GROUP如果 n是一个正整数，如果存在和 n互素的正整数 a满足 an-11(mod n) ，我们说 n是基于 a的伪素数。如果一个数是伪素数，它几乎肯定是素数 .伪素数的应用后面会提到（需要了解费马小定理）。Miller-Rabbin测试CUGB ACM/ICPC GROUP 对于大数的素性判断，目前 Miller-Rabin算法应用最广泛。 一般底数仍然是随机选取，但当待测数不太大时，选择测试底数就
6、有一些技巧了。 比如，如果被测数小于 4 759 123 141，那么只需要测试三个底数 2, 7和 61就足够了。当然，你测试的越多，正确的范围肯定也越大。 如果你每次都用前 7个素数 (2, 3, 5, 7, 11, 13和 17)进行测试，所有不超过 341 550 071 728 320的数都是正确的。大数素性检测CUGB ACM/ICPC GROUP 如果选用 2, 3, 7, 61和 24251作为底数，那么 1016内唯一的强伪素数为 46 856 248 255 981。 这样的一些结论使得 Miller-Rabin算法在 OI(信息学奥林匹克竞赛 )中非常实用。通常认为， Miller-Rabin素性测试的正确率可以令人接受，随机选取 k个底数进行测试算法的失误率大概为 4(-k)。 伪素数：如果 n是一个正整数，并且存在和 n互素的正整数 a满足 an-1 1(mod n), 我们说 n是基于 a的伪素数。如果一个数是伪素数，它几乎肯定是素数。另一方面，如果一个数不是伪素数，它一定不是素数。大数素性检测
