01信息学奥赛CSP-J数学课件-初等数论（上）

- J 初级组 算法 中 数学 》 Day01 - 初等数论 (上 ) else 处理条件不满足 初等数论 初等数论 是研究数的规律，特别是整数性质的数学分 支。它是数论的一个最古老的分支。 初等数论发展历史 毕达哥拉斯 古希腊数学家、哲学家 第一个注重“数”的人 初等数论发展历史 毕达哥拉斯 (公元前 580 — 公元前 590 ) 古希腊数学家、 哲学家 “富二代” 证明了正多面体的个数 毕达哥拉斯定理（勾股定理） 欧几里得 (公元前 330 —公元前 275 ) 古希腊 数学家、 哲学家 “几何之父” 《 几何原本 》 初步建立了整数的整除理论 费 马（ 1601 -1665 ） 法国律师和业余数学家 “业余数学家之王” 费马大定理 欧拉 （ 1707 -1783 ） 瑞士数学家 、自然科学家 13 岁时入读巴塞尔大学 “所有人的老师 ” 数学史上最多产的数学家 各种欧拉公式 高斯（ 1777 -1855 ） 德国数学家、物理学家 正十七边形的尺规作图法 二项式定理的一般形式 “数学王子 ” 世界上第一张地球磁场图 参考教材 陈景润 （ 1933 年 5月 22 日－ 1996 年 3月 19 日 ），福建 福州人，中 国数学家，华罗庚数学奖 得主。“ 1+2” 是哥德巴赫猜想研究的 丰碑。 1+2 ：表达偶数为一个素数及一个不超过两个素数的乘积之和。 课程大纲 整数的整除 性 这些数叫做 正整数 ，又叫做 自然数 (非负整数 ) 这些数叫做 奇数 这些数叫做 偶 数 整数 + 整数 = 整数 整数 -整数 = 整数 整数 × 整数 = 整数 正整数 + 正整数 = 正整数 正整数 × 正整数 = 正整数 这些数叫做 整数（正整数、负整数、 0） Q1 : 如何判定一个数是偶数还是奇数？ Q2 : 什么样的整数除什么样的整数才能得到整数呢？ 因数和倍数 定义 1: ： 设 a,b 是整数， b ≠ 0. 如果有一个整数 c, 它使得 a= bc , 则 a 叫做 b 的倍数， b 叫做 a 的因数。我们有时说， b 能整除 a 或 a 能被 b 整除 ; 12 是 3 的 倍数 ， 3 是 12 的 因数 。 3能 整除 12 ，或 12 能 被 3整除 如果 b 能整除 a, 我们可以 用 b|a 这个符号来表示。如： 素数和复合数 引理 1 : ： 设 a,b 是两个整数 ， b ≠ 0. 则一定有并且只有两个整数 q,r , 可使以下表 达式成立： 素数和复合数 定义 2 : ： 一 个大于 1 的正整数，只能被 1 和它本身整除，不能被其它正整除整除，这 样的正整数叫做素数（也叫做质数）。 eg. 都是 质数 定义 3: ： 一个正整数除了能被 1 和它本身整除以外，还能被另外的正整数整除，这 样的正整数叫做复合数（也叫做合数）。 eg. 都是 合数 Q3 : 如何判定一个数 是 质数 ？ Q4 : 如何判定一个数 是 合数 ？ 素数和复合数 由素数和复合数的定义，可知 , 全体正整数可分为三类 : (1) 1 这个数 (2) 全体素数（质数） (3) 全体复合数（合数） 定义 4: ： 如果一个正整数 a 由一个因数 b, 而 b 又是素数，则 b 就叫做 a 的素因数（质 因数）。 例如， 12 = 3 × 4， 3是素数，而 4不是素数，所以 3是 12 的素因数（质因数）。 而 4不是 12 的素因数。 Q5 : 合数由多少个 ？ 定义 4: ： 如果一个正整数 a 由一个因数 b, 而 b 又是素数，则 b 就叫做 a 的素因数（质 因数）。 例如， 12 = 3 × 4， 3是素数，而 4不是素数，所以 3是 12 的素因数（质因数）。 而 4不是 12 的素因数。 素数和复合数 引理 1 : ： 如果 a 是一个 大于 1 的整数，则 a 的大于 1 的最小因数一定是素数。 （可以分素数和合数讨论证明） 这个引理说明了：任何大于 1 的整数都至少有一个素因数。 素数和复合数 引理 2 : ： 如果 a 是一个大于 1 的整数，而所有 ≤ a的 素数都除不尽 a, 则 a 是素数。 Step 1: 证明（ 1） ：如果 a被 > 1 而 ≤ a的整数都除不尽，则 a是素数 bool isPrime (int n){ if (n == 0 || n == 1) return false ; for (int i = 2; i <= sqrt(n); i++){ if ( n%i == 0){ return false ; } } return true ; } 假设 a是合数，则 a= bc , 而 a被 > 1 而 ≤ a的整数都除 不尽，则 b> a, c> a,则 bc >a, 这与 bc =a 是矛盾的。 开根号法判定质数 素数和复合数 引理 2 : ： 如果 a 是一个大于 1 的整数，而所有 ≤ a的 素数都除不尽 a, 则 a 是素数。 Step 2: 证明 （ 2） ：所有的素数除不尽即可 bool isPrime (int n){ if (n == 0 || n == 1) return false ; for (int i = 2; i <= sqrt(n); i++){ if ( n%i == 0){ return false ; } } return true ; } 假设 a是合数 ，则 a一定有 > 1 而 ≤ a的 因数，有引理 1可知大于 1的最小因数一 定是素数。 开根号法判定 质数（如何优化？） 素数的分布 在 1到 100 中间有 25 个素数， 在 1到 1000 中间有 168 个素数， 在 1000 到 2000 中间有 135 个素数， 在 2000 到 3000 中间有 127 个素数， 在 3000 到 4000 中间有 120 个素数， 在 4000 到 5000 中问有 119 个素数， 在 5000 到 10000 中间有 560 个素数 . 到目前为止所知道的