1、05 循环分支运用循环分支运用 程序设计基础 2 home back first prev next last 本节目标本节目标 循环分支综合运用循环分支综合运用 最大公约数最大公约数 最小公倍数最小公倍数 求素数求素数 穷举法应用穷举法应用 3 home back first prev next last 最大公约数最大公约数 5-1 如果两个数都能够被一个数整除，则这个数如果两个数都能够被一个数整除，则这个数 就是两个数的公约数。就是两个数的公约数。 如，如，8 和和 4 都可以被都可以被2整除，整除，2就是就是 8 和和 4的公约的公约 数。数。 公约数中最大的称为最大公约数。公约数中最
2、大的称为最大公约数。 如如 8 和和 4 都可以被都可以被2或或4整除，整除，2和和4都是都是8 和和 4的的 公约数。其中公约数。其中4最大，最大，4就是就是8 和和 4的最大公约数。的最大公约数。 4 home back first prev next last 最大公约数最大公约数 5-2 编程求编程求204和和85的最大公约数，有两种办法的最大公约数，有两种办法 可以解决这个问题可以解决这个问题 应用穷举法。穷举法也叫枚举法或列举法。这应用穷举法。穷举法也叫枚举法或列举法。这 种方法的主要思想是：在要解决的问题是由有种方法的主要思想是：在要解决的问题是由有 限种情况组成时，把所有的情况
3、一一列举出来，限种情况组成时，把所有的情况一一列举出来， 再对其一一进行判断和解决。再对其一一进行判断和解决。 依次判断从依次判断从1到到85之间的数字，是否能够同时整之间的数字，是否能够同时整 除除204和和85 答案应该是答案应该是17 5 home back first prev next last 最大公约数最大公约数 5-3 6 home back first prev next last 最大公约数最大公约数 5-4 应用辗转相除法。应用辗转相除法。 辗转相除法基于如下原理：两个整数的最大公辗转相除法基于如下原理：两个整数的最大公 约数等于其中较小的数和两数的差的最大公约约数等于其
4、中较小的数和两数的差的最大公约 数。数。 例如，例如，252和和105的最大公约数是的最大公约数是21（252 = 21 12；105 = 21 5）；因为）；因为252 105 = 147，所以，所以 147和和105的最大公约数也是的最大公约数也是21。在这个过程中，。在这个过程中， 较大的数缩小了，所以继续进行同样的计算可较大的数缩小了，所以继续进行同样的计算可 以不断缩小这两个数直至其中一个变成零。这以不断缩小这两个数直至其中一个变成零。这 时，所剩下的还没有变成零的数就是两数的最时，所剩下的还没有变成零的数就是两数的最 大公约数。大公约数。 7 home back first pre
5、v next last 最大公约数最大公约数 5-5 你认为两种算法，哪一种比较好？为什么？你认为两种算法，哪一种比较好？为什么？ 8 home back first prev next last 最小公倍数最小公倍数 3-1 如果两个数都可以整除一个数，则这个数就如果两个数都可以整除一个数，则这个数就 是那两个数的公倍数。是那两个数的公倍数。 如如 6和和8都可以整除都可以整除48，48就是就是6和和8的公倍数。的公倍数。 公倍数中最小的称为最小公倍数。如公倍数中最小的称为最小公倍数。如 48、24都都 是是6和和8的公倍数，的公倍数，24是公倍数中最小的，是是公倍数中最小的，是6和和 8的
6、最小公倍数。的最小公倍数。 编程求编程求204和和85的最小公倍数。（答案应该的最小公倍数。（答案应该 是是1020） 一种办法是穷举法，自己尝试编程序一种办法是穷举法，自己尝试编程序 9 home back first prev next last 最小公倍数最小公倍数 3-2 也可以借助最大公约数求最小公倍数，步骤：也可以借助最大公约数求最小公倍数，步骤： 一、利用辗除法或其它方法求得最大公约数；一、利用辗除法或其它方法求得最大公约数； 二、二、 最小公倍数等于两数之积除以最大公约数。最小公倍数等于两数之积除以最大公约数。 举例：举例：12和和8的最大公约数为的最大公约数为4 128/4=
7、24 两数的最小公倍数是两数的最小公倍数是24 10 home back first prev next last 最小公倍数最小公倍数 3-3 你认为两种算法，哪一你认为两种算法，哪一 种比较好？为什么？种比较好？为什么？ 11 home back first prev next last 求素数求素数 4-1 素数，又叫质数，是除了素数，又叫质数，是除了1和它本身之外再不能被和它本身之外再不能被 其他数整除的自然数。其他数整除的自然数。 由于找不到一个通项公式来表示所有的素数，所由于找不到一个通项公式来表示所有的素数，所 以对于数学家来说，素数一直是一个未解之谜。以对于数学家来说，素数一直
8、是一个未解之谜。 求素数的方法有很多种，最简单的方法是根据素求素数的方法有很多种，最简单的方法是根据素 数的定义来求。对于一个自然数数的定义来求。对于一个自然数N，用大于，用大于1小于小于N 的各个自然数都去除一下的各个自然数都去除一下N，如果都除不尽，则，如果都除不尽，则N 为素数，否则为素数，否则N为合数。但是，如果用素数定义的为合数。但是，如果用素数定义的 方法来编制计算机程序，它的效率一定是非常低方法来编制计算机程序，它的效率一定是非常低 的，其中有许多地方都值得改进。的，其中有许多地方都值得改进。 12 home back first prev next last 求素数求素数 4-
9、2 利用素数定义，编程求利用素数定义，编程求50个素数个素数 试着改进算法，提高效率试着改进算法，提高效率 13 home back first prev next last 求素数求素数 4-3 改进建议：改进建议： 第一，对于一个自然数第一，对于一个自然数N，只要能被一个非，只要能被一个非1非非 自身的数整除，它就肯定不是素数，所以不必自身的数整除，它就肯定不是素数，所以不必 再用其他的数去除。再用其他的数去除。 第二，对于第二，对于N来说，只需用小于来说，只需用小于N的素数去除就的素数去除就 可以了。例如，如果可以了。例如，如果N能被能被15整除，实际上就能整除，实际上就能 被被3和和5整除，如果整除，如果N不能被不能被3和和5整除，那么整除，那么N也也 决不会被决不会被15整除。整除。 第三，对于第三，对于N来说，不必用从来说，不必用从2到到N一一1的所有素的所有素 数去除，只需用小于等于数去除，只需用小于等于N(根号根号N)的所有素数的所有素数 去除就可以了。去除就可以了。 14 home back first prev next last 求素数求素数 4-4 15 home back first prev next last 总结总结 循环分支综合运用循环分支综合运用 最大公约数最大公约数 最小公倍数最小公倍数 求素数求素数 穷举法应用穷举法应用
