1、ACM数论问题湖南工业大学数论基本知识信息学竞赛和程序设计竞赛中常考的数论知识关于素数和整除，关键在于灵活应用v 整除 :如果 a和 b是整数， a0 ，若有整数 c使 b ac，就说 a整除 b。在 a整除 b时，记 a是 b的一个因子， b是 a的倍数。用符号 ab 表示 a整除 b， a不能整除 b记为 a b 。v 整除基本性质有：（ 1）若 ab ， ac ，则 a （ b c）（ 2）若 ab ，则对所有整数 c， abc（ 3）若 ab ， bc ，则 ac （传递性）ACM团队湖南工业大学数论基本知识v 素数（ prime）和合数（ compound），如果一个整数 p只有 1
2、和 p两个因子，则 p为素数，不为素数的其它数为合数。 如果 n为合数，则 n必有一个小于或等于 n的平方根的数因子。v 给出一个数 n，如何判断它是不是素数？ 朴素的判别法 从 2开始试除小于 n的所有自然数，时间复杂度为O(n). 如果 a是 n的因子，那么 n/a也是 n的因子，所以如果 n有一个大于 1的真因子，则它必有一个不大于 n1/2的因子，时间复杂度 O(n1/2)。v 算术基本定理：每个正整数都可以唯一地表示成素数的乘积。其中素数因子从小到大依次出现。v 最大公约数 gcd(a, b)v 最小公倍数 lcm(a, b)v ab gcd(a, b)lcm(a , b)v 如果
3、gcd(a, b)=1，则 a与 b互素。ACM团队湖南工业大学素数算法 v 最一般的求解 n以内素数的算法。复杂度是 o(n*sqrt(n)，适合 n很小num = 0; for(i=2; isqrt(i) ) primenum+ = i; ACM团队湖南工业大学素数v 当 n很大的时候，比如 n=10,000,000时，n*sqrt(n)30,000,000,000,数量级相当大v思考如何改进？ACM团队湖南工业大学素数筛法v 最简单的素数筛法 开一个大的 bool型数组 prime，大小就是 n+1就可以了 .先把所有的下标为奇数的标为 true,下标为偶数的标为false. 把奇数的倍
4、数设为 false. 见代码 -prime_choice.cv 改进的素数筛法 bool型数组里面只存奇数不存偶数。如定义 primeN,则 0表示 3， 1表示 5， 2表示 7， 3表示 9.。如果 prime0为true,则表示 3时素数。 prime3为 false意味着 9是合数，每个单元代表的数是 2*i+3。 欲求 n以内的素数，就先把 sqrt(n)内的素数求出来，用已经求得的素数来筛出后面的合数。 ACM团队湖南工业大学数论基本知识v 如何求出 1 n中的所有素数？Eraosthenes（爱拉托斯尼筛法）筛法：每次求出一个新的素数，就把 n以内的它的所有倍数都筛去。经典的 E
5、raosthenes筛法：for (int i = 2; i * i 0 则 an-11(mod n) 或 an-1 mod n =1 即 (an-1-1)/n=0 2(5-1)-1=15,15|5. 2(3-1)-1=3,3|3.但很多都是素数，如 3，5， 7， 29， 31 1819 年数学家萨鲁斯找到了反例： 2(341-1)-1|341,而 341=11*31是合数， 341就成了第一个伪素数。以后又发现了许多伪素数： 561 645 1105 1387 1729 ACM团队湖南工业大学伪素数v 伪素数的一个用途 利用伪素数表来判定一个奇数 n是否为素数。 如果 n不能整除 2(n-
6、1) 1，则据费马小定理知， n必为合数； 如果 n能整除 2(n-1) 1 ，且 n在伪素数表中，则 n为合数，否则为素数。 这种方法的关键就在于按伪素数表去掉伪素数，而这要求伪素数在能整除 2(n-1) 1的数中相当少才行，这就是当 n整除 2(n-1) 1时， n是合数的比例问题。 在前 10亿个自然数中，共有 50847534个素数，而只有以 2为底的伪素数 5597个，即在此范围内 n整除 2n-1 1产生合数的可能性只有 0.011%。在 10亿之内， n整除 2(n-1) 1同时整除 3(n-1) 1 的合数 n只有 1272个，即此时产生合数的可能性只有 0.0025%。ACM团队
