数论小站.pptxVIP

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