第13周阶乘因子与互素数.ppt

北京工商大学　　陈红倩 阶乘因子与互素数 陈红倩chenhq123@ * 上周作业 上周内容 素数 试除法 Eratosthenes筛法 梅森素数 孪生素数 RSA加密 筛法 Eratosthenes算法 只需要4遍筛选，就可以求出所有100以内的所有素数 10*10 = 100 输出1w以内的所有素数（筛法） 求出1w以内的所有孪生素数 编程实现？ 1w以内1229个素数 哥德巴赫猜想 任意一个大于2的偶数，都可以表示为两个素数之和（1+1） 陈景润 （1+2） 任何一个大偶数都可以表示成一个素数与另一个素因子不超过2个的数之和 阶乘因子 阶乘因子合数 n！= 1 * 2 * … * n n!的范围 n!的范围 k ( n+1 – k ) = k (n+1) – k2 = 2 * k * ( ) – k2 = ( )2 – [ ( )2 – 2 * k * ( ) + k2 ] = ( ) 2 – ( – k )2 n!的范围 n = k ( n+1 – k ) = ( ) 2 nn = (n!)2 = ( )2n nn/2 = n! = ( )n Stirling公式 素数之积 素数是所有正整数的组成部分 任何正整数，都能表示成若干个素数之积 且素数的序列是唯一的 素因子p的幂指数 n! 进行素因子分解 素因子分解中，素因子p的幂指数 如 10! 中 素因子 2 的指数是几？ 素因子p的幂指数 素因子p的幂指数 素因子p的幂指数 32 16 8 4 2 1 素因子2的幂指数 100 = (1100100)2 (26-1) + (25-1) + (22-1) 次 近似求 互素性 互素 互素性质 互素性质 最简分数集合 Stern-Brocot树 Stern-Brocot树 Stern-Brocot树 为什么可以？ 恰好只出现一次，无两次重复 为什么是最简形式？ 如何保证无漏掉的情形？ 为什么可以？ 恰好只出现一次，无两次重复 为什么是最简形式？ 如何保证无漏掉的情形？ 为什么可以？ 恰好只出现一次，无两次重复 为什么可以？ 2. 为什么是最简形式？ 为什么可以？ 为什么可以？ Farcy序列 Farcy序列 Farcy序列 第二种构造方法 再看定理 Stern-Brocot树表示法 Stern-Brocot树表示法 Stern-Brocot树表示法 Stern-Brocot树表示法 给定分数，反求Stern-Brocot树表示法 Stern-Brocot树表示法 给定5/7，反求Stern-Brocot树表示法 e=2.71828… e=2.71828… 欧几里德算法 本周作业 素因子p的幂指数 Stern-Brocot树 Farcy序列 第二种构造方法 欧几里德算法 END 3. 如何保证无漏掉的情形？ 3. 如何保证无漏掉的情形？ 任意给定分数(a/b),都能最终获得 直到 f(S)为1时停止 f(S) =1是根节点 * * 16 8 4 2 1 2 1 mp指m中素数因子p的幂指数 *