数学知识-质数.pptVIP

练习： 例题 喜欢摇头的数学牛(cogs 1261) 整数合并(cogs 487) 数学知识-数论-质数 河南省实验中学信息组 质数 质数的判定 数字 约数 36 1 2 3 4 6 9 12 18 36 37 1 37 质数的筛选 埃氏筛 埃氏筛(Eratosthenes筛法) 思想：任意正整数x的倍数2*x,3*x, ?都不是质数。 ? 从2开始遍历每一个数x，如果它是质数，把它的倍数2x, 3x, ? ,?n ? x? ?x 标记为合数。 ? 当扫描到一个数x时，若它尚未标记，则它不能被2~x?1之间的任何数整除，该数就是质数。 ? 埃氏筛的时间复杂度： 例如找出100内所有素数，如下图： 首先2的倍数筛去 3的倍数筛去 12又被筛了一次，某些数字有重复筛的问题。 5的倍数筛去 7的倍数筛去 还需要继续吗？11*11 =121 超过了100 欧氏筛 欧氏筛(欧拉筛法/线性筛法) ? 经过优化后的埃氏筛仍会重复筛除合数。例如，12既会被2筛也会被3筛，这就出现了重复筛选；再例如，30被2、3、5各筛一次。 问题：是否存在线性筛法，让每个合数只筛一次？ 欧拉筛法就是一种线性筛法。? ? 考虑：有什么办法让每个合数只被筛一次？ 我们知道合数可以质因式分解，最小质因子是唯一的，我们能不能让每个合数被它的最小质因子筛掉？ 以45以内的所有数为例： 质数：2、3、5、7、11、13、17、19、23、29、31、37、41、43 合数：4、6、8、9、10、12、14、15、16、18、20、21、22、24、25、26、27、28、30、32、33、34、35、36、38、39、40、42、44、45 将所有合数分解成最小质因子做被乘数的形式，确保被乘数小于等于乘数。 被乘数相同的写一行，如下： 2*2、2*3、2*4、2*5、2*6、2*7、2*8、2*9、2*10、2*11、2*12、2*13、2*14、2*15、2*16、2*17、2*18、2*19、2*20、2*21、2*22 3*3、3*5、3*7、3*9、3*11、3*13、3*15 5*5、5*7、5*9 问题： 怎样才能按照上面的顺序进行筛？ 换个顺序写，乘数相同的写一行，被乘数小于等于乘数 2*2 2*3、3*3 2*4 2*5、3*5、5*5 2*6 2*7、3*7、5*7 2*8 2*9、3*9 2*10 2*11、3*11 2*12 2*13、3*13 2*14 2*15、3*15 2*16 2*17 …… 2*22 当乘数是被乘数的倍数时，停止筛除。3*4不会出现，4中必有2这个因子，而23，会在2*6时筛除 思路： 以乘数作为循环变量i，如果i没有被标记，i记入质数表，质数表中现有质数与i乘积的数则为合数，将其标记筛掉， 注意当乘数是被乘数的倍数时停止i的处理，开始筛i+1 为什么循环到n，而不是n/i ? 欧氏筛还有另外一种写法 设数组v记录每个数的最小质因子，即该数被哪个数筛，我们按照如下步骤维护v: ? 依次考虑2~N之间的每一个数i； ? 如果v[i] = 0，说明i未被筛过，即为质数，把它存下来，并令v[i]=i； ? 如果v[i] ≠ 0，扫描不大于v[i]的每个质数p，令v[i*p] =p。因为p≤v[i]，而p是从最小的质数开始扫描的，所以p就是合数i?p的最小质因子。 ? 因为每个合数i?p只会被他的最小质因子p筛一次，时间复杂度为 O(N)。 算术基本定理 质因数分解 质因数分解 质因数分解 【例】PRIME DISTANCE(COGS3478) 给定两个整数L,R(1≤L≤R≤231, R?L≤106)，求闭区间[L,R]内相邻两个质数的差的最大是多少，输出这两个质数。(输入数据有多组) ? 输入格式：多行，每行两个整数L,R。 ? 输出格式：多行，每行连个整数表示差最大的两个质数(小数在前，大数在后)，如果有多组解输出较小的，如果没有解输出“no adjacent primes”。 输入样例： 输出样例： 2 17 7 11 14 17 no adjacent primes 样例解释：2~17中的质数有2、3、5、7、11、13、17，相差最大的质数对有7 11 和 13 17，输出7 11 14~17中的质数有17，不存在质数对。