Matlab求两个数最大公约数

在命令窗口输入两个自然数，输出它们的最大公约数（不要用matlab自带的求最小公倍数和最大公约数的函数。利用求同余的函数判断是否整除）

function greatestcommondivisor()

%求两个数的最大公约数

a=input('请输入正整数a:');

b=input('请输入正整数b:');

%先求把两个数中最小的值赋给tem

if a>b

tem=b;

else tem=a;

end

%进行步长为1的倒序循环，保证求得的公约数是最大的

for n=tem:-1:1

%c和d分别是a、b除以m的余数，c、d同时为零时，m即为最大公约数c=rem(b,n);

d=rem(a,n);

if c==0&d==0

disp(['最大公约数为;',num2str(n)])

break;

end

end

c语言程序设计方案求两个数最大公约数

1，写两个函数，分别求两个整数的最大公约数和最小公倍数，用主函数调用这两个函数，并输出结果。这两个数由键盘输入。 程序设计： #include int hcf(int x,int y) {int t; if(x

#include void g_two(double a,double b,double c) {double x1,x2; x1=(-b+sqrt(b*b-4*a*c))/(2*a); x2=(-b-sqrt(b*b-4*a*c))/(2*a); printf("方程的两个根为：x1=%f\nx2=%f\n",x1,x2); } void g_one(double a,double b,double c) {double x; x=(-b)/(2*a); printf("方程的两个根为：x1=x2=%f\n",x); } void g_zone(double a,double b,double c) { printf("无解\n"); } void main() {void g_two(double,double,double); void g_one(double,double,double); void g_zone(double,double,double); double a,b,c,t; printf("请输入a、b、c的值："); scanf("%lf%lf%lf",&a,&b,&c); t=b*b-4*a*c; if(t>0) g_two(a,b,c); else if(t==0) g_one(a,b,c); else g_zone(a,b,c); } 运行结果：

c++实现计算任意多个三位数的最大公约数,直到输入-999为止,调用子函数求最大公约数

#pragma warning(disable:4786) #include #include #include #include using namespace std; #ifndef SYSOUT const char *SYSOUT = "999"; //退出标示 const int SYSFAILED = -1; //系统错误码 const int SYSNUMLENGTH = 3; //输入的数据长度限制 #endif //判断用户输入字符是否为数字 bool IsAllNum(const char* resStr); //计算最大公约数 int GetMaxDivissor(set *pSetNum,int nMin); //该函数去除输入前端“0” void GetStingTrim(string *pStr); int main() { //----------------------------------------------------------------------------------------- //程序变量 char szNum[4] = {0}; set setNum; //用户输入数据数组 string buffer; int nMax = 0; //用户输入最大数 int nMin = 0; //用户输入最小数 bool isNum = false; //是否为数字 int count = 0; //记录用户输入数据量 int nTmp = 0; //用于存储临时数据 char szNotice[100] = {0}; //----------------------------------------------------------------------------------------- //用户输入控制 while(strcmp(buffer.c_str(),SYSOUT) != 0) { buffer = ""; memset(szNotice,0,sizeof(szNotice)); sprintf(szNotice,"Please Enter Your %dNum:",count+1); cout<

最大公约数的算法

. 1、查找约数法． 先分别找出每个数的所有约数，再从两个数的约数中找出公有的约数，其中最大的一个就是最大公约数． 例如，求12和30的最大公约数． 12的约数有：1、2、3、4、6、12； 30的约数有：1、2、3、5、6、10、15、30． 12和30的公约数有：1、2、3、6，其中6就是12和30的最大公约数． 2 更相减损术 《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 翻译成现代语言如下： 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。 3、辗转相除法． 当两个数都较大时，采用辗转相除法比较方便．其方法是： 以小数除大数，如果能整除，那么小数就是所求的最大公约数．否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数．依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数． 例如：求4453和5767的最大公约数时，可作如下除法． 5767÷4453＝1余1314 4453÷1314＝3余511 1314÷511＝2余292 511÷292＝1余219 292÷219＝1余73

219÷73＝3 于是得知，5767和4453的最大公约数是73． 辗转相除法适用比较广，比短除法要好得多，它能保证求出任意两个数的最大公约数．4、求差判定法． 如果两个数相差不大，可以用大数减去小数，所得的差与小数的最大公约数就是原来两个数的最大公约数．例如：求78和60的最大公约数．78－60＝18，18和60的最大公约数是6，所以78和60的最大公约数是6． 如果两个数相差较大，可以用大数减去小数的若干倍，一直减到差比小数小为止，差和小数的最大公约数就是原来两数的最大公约数．例如：求92和16的最大公约数．92－16＝76，76－16＝60，60－16＝44，44－16＝28，28－16＝12，12和16的最大公约数是4，所以92和16的最大公约数就是4． 5、分解因式法． 先分别把两个数分解质因数，再找出它们全部公有的质因数，然后把这些公有质因数相乘，得到的积就是这两个数的最大公约数． 例如：求125和300的最大公约数．因为125＝5×5×5，300＝2×2×3×5×5，所以125和300的最大公约数是5×5＝25． 6、短除法． 为了简便，将两个数的分解过程用同一个短除法来表示，那么最大公约数就是所有除数的乘积． 例如：求180和324的最大公约数． 因为： 5和9互质，所以180和324的最大公约数是4×9＝36． 7、除法法． 当两个数中较小的数是质数时，可采用除法求解．即用较大的数除以较小的数，如果能够整除，则较小的数是这两个数的最大公约数． 例如：求19和152，13和273的最大公约数．因为152÷19＝8，273÷13＝21．（19和13都是质数．）所以19和152的最大公约数是19，13和273的最大公约数是13．

matlab最大公约数 三种算法

算法设计与分析 11信本余启盛 118632011004 一、上机目的及内容 1.上机内容 求两个自然数m和n的最大公约数。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线图 （1）至少设计出三个版本的求最大公约数算法； （2）对所设计的算法采用大O符号进行时间复杂性分析； （3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件matlab .2008 四、实验方法、步骤（或：程序代码或操作过程） 实验采用三种方法求最大公约数 1、连续整数检测法。 2、欧几里得算法 3、蛮力法（短除法） 根据实现提示写代码并分析代码的时间复杂度： 算法一：连续整数检测法。 CommFactor1 输入：两个自然数m和n 输出：m和n的最大公约数 1.判断m和n哪个数小，t=min（m，n） 2.如果m%t==0&&n%t==0 ，结束 2.1 如果t不是m和n的公因子，则t=t-1; 3. 输出t ;

根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2; 算法二：欧几里德算法 CommFactor2 输入：两个自然数m和n 输出：m和n的最大公约数 1. r = m % n; 2. 循环直到r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出n ; 根据代码辗转相除得到欧几里得的: O(n)= log n 算法三：蛮力法（短除法） CommFactor3 输入：两个自然数m和n 输出：m和n的最大公约数 1.factor=1； 2.循环变量i从2-min（m，n），执行下述操作： 2.1 如果i是m和n的公因子，则执行下述操作： 2.1.1 factor=factor*i； 2.1.2 m = m / i; n = n / i; 2.2 如果i不是m和n的公因子，则i=i+1； 3. 输出factor； 根据代码考虑最坏情况他们的最大公约数，循环做了i-1次;最好情况是只做了1次，可以得出: O（n）=n/2; MATLAB程序代码： main.m x=fix(rand(1,1000)*1000); y=fix(rand(1,1000)*1000); for i=1:1000 A(i)=CommFactor2(x(i),y(i)); end x=x'; y=y';

汇编程序：求两个正整数的最大公约数

CRLF MACRO MOV AH,02H MOV DL,0DH INT 21H MOV AH,02H MOV DL,0AH INT 21H ENDM data segment M dw 8 N DW 16 result dw 0 y dw 10 output1 dw 0 K dw 0 s1 db"Please input a number as 'M': $" s2 db"Please input a number as 'N': $" s3 db"The result is : $" data ends stack segment s dw 1000 dup(?) stack ends code segment assume cs:code,ds:data,ss:stack start: push ds mov ax,0 push ax mov ax,data mov ds,ax lea dx,s1 mov ah,09h int 21h call intput mov ax,K

mov M,ax mov K,0 crlf lea dx,s2 mov ah,09h int 21h call intput mov ax,K mov N,ax mov K,0 crlf call ouji mov ax,result mov output1,ax lea dx,s3 mov ah,09h int 21h call output mov output1,0 ret ouji proc near xor dx,dx mov ax,m mov bx,n T: cmp ax,bx jge U xchg ax,bx U: mov cx,ax div bx cmp dx,0 jnz G mov result,bx

用短除法求两个数的最大公因数和最小公倍数王现辉

用短除法求两个数的最大公因数和最小公倍数 教学内容：五年级数学下册补充内容。 教学目标:１、学生会用短除法求两个数的最大公因数 2、学生会用短除法求两个数的最小公倍数 教学重、难点：理解并学会短除法 学情分析:学生在前面的学习中已经掌握了用列举法求两个数的最大公因数和最小公倍数,但学生在用列举法找两个数的公因数和最小公倍数时，容易出错，不是找不齐一个数的因数,就是找出了所有公因数和一部分公倍数，对最大公因数和最小公倍数还是视而不见。其次，教材中要求学生掌握的方法具有明显的局限性,遇到大的数学生就不会找了,错误率就很高，鉴于这种情况很有必要补充用短除法求两个数的最大公因数和最小公倍数。 教学过程： 一、复习旧知 1、口答下面问题 （１）6和12的最大公因数和最小公倍数分别是多少? （2)5和7的最大公因数和最小公倍数分别是多少？ 师:同学们回答都很正确,倍数关系的两个数，最大公因数是较小的数，最小公倍数是较大的数。互质关系的两个数，最大公因数是１，最小

公倍数是它们的乘积。对于没有这两种关系的两个数，你会求最小公倍数和最大公因数吗？ 2、用列举法求32和48的最大公约数和最小公倍数。 解：32的约数有:１２ 4 8 16 32 ４8的约数有:1 2 3 4 6 ８1 ２１6 ２4 ４8 则32和4８的最大公约数为１6。 3２的倍数有:３２６4 9６128 １60 1９ ２２24…… 4８的倍数有:48 9６１44 １９2 2４ ０288 ３３6…… 则3２和４８的最小公倍数为９6。 学生独立完成，师生集体订正。 师:同学们，你们个别同学用列举法找出的最大公因数和最小公倍数是错误的,原因是什么？(生1：3２和4８的数字太大了。生2：用列举法太麻烦了。) 师：我们今天就学习一种简便的求最大公因数和最小公倍数的方法。 板书课题：用短除法求两个数的最大公因数和最小公倍数 二、讲授新知 1、介绍短除号

用迭代法求两个数的最大公约数和最小公倍数

用迭代法求两个数的最大公约数和最小公倍数 化工09110605 摘要：迭代法是一种循环控制语句和循环结构程序的设计方法。在计算机解决问题的时候，总希望从复杂的问题中找到规律，并归结为简单问题的重复，发挥其擅长重复运算的特点，让它重复执行一组语句，直到满足给定条件为止。因此，c语言提供了重复操作的语句，由这些语句构成的程序称为循环结构。本文就是采用迭代法，利用c语言中提供的重复语句，求得两个数的最大公约数和最小公倍数。 关键词：循环语句；循环结构；迭代法；最大公约数和最小公倍数 Iterative Method with the greatest common divisor and least common multiple of two numbers Chemical 09110605 W ANG Meng Abstract: The iterative method is a loop control statement and loop structure design process.When the computer to solve the problem, hoping to find from the law of complex issues and boil down to a simple repetition of questions, to play the good characteristics of repeat operation, let it repeat a set of statements until the date that satisfies the given conditions. Therefore, c language repeat the statement provided by these statements constitute the program is called loop structure. This is the iterative method, using c language provided by the repeated statement, obtained the greatest common divisor and least common multiple of two numbers. Key words:loop; loop structure; iteration; greatest common divisor and least common multiple

求最大公约数教学设计

求最大公约数教案 道真县中等职业学校张学东 教学目标： 1．使学生进一步理解和掌握公约数和最大公约数的意义。 2．使学生理解和掌握用短除法、分解质因数的方法两个数的最大公约数的算理。 教学难点：用分解质因数的方法求两个数的最大公约数的算理。 教学设计： 一约数 【引例】看下面的式子： 18÷6 25÷5 24÷3 99÷11 169÷13这些除式中，商都是整数，余数为0.我们在数的整除中已经知道，这些除式都是整除式。 【小结】如果一个整数a除以整数b（b≠0）除得的商正好是整数而没有余数，那么我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。 上式中6是18的约数，5是25的约数，3是24的约数，11是99的约数，13是169的约数……，显然约数只存在于整除式中，故不是整除式就不存在约数。 二公约数及最大公约数 【引例】看下面的式子：

48÷8 24 ÷8 56÷8 ，显然，这些都是整除式，8是48、 24、56、这些所有整数的约数。 【小结】如果一个整数同时是几个整数的约数，那么就称这个 整数是它们的公约数。 公约数亦称公因数，公约数中最大的我们称它为最大公约数，若a 、b 的最大公约数为c ， 三 公约数与最大公约数的求法 求最大公约数的求法一般有：枚举法、短除法、分解质因数法、 1、短除法： 【讲解】 短除符号就像一个倒过来的除号，短除法就是先写出要求最大公因数的两个数A 、B ，再画一个短除号，接着在原本写除数的位置写两个数公有的质因数Z （通常从最小的质因数开始），然后在短除号的下方写出这两个数被Z 整除的商a 、b ，对a 、b 重复以上步骤，以此类推，直到最后的商互质为止，再把所有的除数相乘，其积即为A 、B 的最大公约数。 例1： 用短除法求12和18的最大公约数。 解:∵ ∴12和18的最大公约数为2×3=6 2、分解质因数法 【讲解】将要求最大公因数的两个数A 、B 分别分解质因数，再从中找出A 、B 公有的质因数，把这些公有的质因数相乘，即得到A 、2 12 18 6 9 3

三种方法求最大公约数200910405429

昆明理工大学信息工程与自动化学院学生实验报告 （2011 —2012 学年第 1 学期） 课程名称：算法设计与分析开课实验室：信自楼应用、网络机房445 2011 年10月 19日年级、专业、班计科094 学号200910405429 姓名徐章林成绩 实验项目名称求最大公约数指导教师吴霖 教师评语该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力： A.强□ B.中等□ C.差□ 该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范： A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录： A.详细□ B.一般□ C.没有□ 教师签名： 年月日 一、上机目的及内容 1.上机内容 求两个自然数m和n的最大公约数。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 三、实验原理及基本技术路线图（方框原理图或程序流程图）

（1）分解质因数法的流程分析如下图： （2）连续整数检测法流程分析如下图：

（3）殴几里德流程分析如下图： 四、实验方法、步骤（或：程序代码或操作过程） /*--------------------用多种方法计算两个数的最大公约数----------------------*/ /*-----------------作者：200910405429--------开发环境：DEV C++----------------*/ #include "stdio.h" #include "conio.h" #include"time.h" /*------------------------以下是分解质因数法--------------------------------*/ int gcd_factor(int a,int b) { int k=1,i,temp; { temp=a; a=b; b=temp; } if(a%b==0) { return b; } else { for(i=2;i

人教版五年级数学下册 《求两个数的最大公因数》教学设计

《求两个数的最大公因数》教学设计 学习内容 教科书第79——81页例1、例2，第80、81页“做一做”，练习十五第1——3题。 学习目标 1. 理解并掌握公因数和最大公因数的意义。 2. 经历探索求两个数的最大公因数的方法的过程，能正确地求两个数的最大公因数。 3. 通过学习，提高自己解决实际问题的能力。 学习重点 公因数和最大公因数的意义，会求两个数的最大公因数。 学习难点 求最大公因数的方法。 教学过程 一、利用旧知，初步理解 1、找出16和20的因数分别填写到圆圈内。

2、如果把这两个圆圈交叉，把16和20的因数填写到这两个交叉的圆圈中，你能给他们找到位置吗？中间这部分该如何填写呢？ 3、交流答案。 4、中间这部分填写的1、2、4就是16和20的公因数，其中的4就是它们的最大公因数。你能用自己的话说说什么是公因数，什么是最大公因数吗？ 5、这节课我们就来一起研究找两个数的最大公因数。 二、自主学习，探究规律 1、出示：21和24 你能找出21和24的公因数和最大公因数吗？ 2、汇报： 你是怎么找出的？有不同的方法吗？找最大公因数时在哪些数里找？ 3、出示：找出下面每组数的最大公因数：（小组研究交流） 8和16 20和10 1和14 5和7 3和11 4、汇报：分别观察这几组数的特点，你有什么发现？你还能找出这样的一组数吗？

（根据实际情况，本课教学还是把旧教材中互质数、分解质因数、短除法纳进来，以利于最大公因数的教学。） 三、运用规律，巩固知识 请你找出下列分数分子和分母的最大公因数： 8/12 6/18 8/9 5/11 15/21 1/20 13/26 四、拓展应用，训练思维 1、面包店的师傅制作了18个巧克力蛋挞，24个草莓蛋挞。面点师傅现在要把这两种糕点分别装到包装盒里摆到柜台上出售，每一盒数目相同，而且没有剩余。你知道都可以几个装一盒吗？哪种最实用呢？你是怎么想的？ 2、老师新买的房子，房子的厨房长30分米,宽24分米,要铺正方形瓷砖,需要边长为多少分米的方砖才能铺得既整齐又节约?你是怎么想的？选择哪种比较合适呢？ 3、我们一起来做个游戏，学号是1的同学起立，表示你学号的数字和1的最大公因数是1的同学起立。这说明什么？2号同学起立，代表你学号的数字和2的最大公因数是1的同学起立，你们都是几号？你有什么发现？在你的小组找一找两个同学之间学号数字的最大公因数。 求两个数的最大公因数有个小窍门： 1.连续的两个自然数的最大公因数一定是1。

短除法求两个数的最大公因数和最小公倍数

用短除法求两个数的最大公因数和最小公倍数（原创补充教程） 做一做 把下列这些数用短除法分解成用素数连乘的形式。 10＝（）×（） 24＝（）×（）×（）×（） 20＝（）×（）×（） 30＝（）×（）×（） 学一学 用短除法求18和24的最大公因数和最小公倍数。 2 18 24 …………先同时除以公因数2 3 9 12 …………再同时除以公因数3 3 4 ……除到两个商只有公因数1为止。 把所有的除数相乘，得到：18和24的最大公因数是2×3 ＝6，可表示为（18,24）＝2×3＝6。 把所有的除数和最后的两个商连乘，得到：18和24的最小公倍数是2×3×3×4＝72，可表示为[18,24]＝2×3×3×4＝72。 用短除法求两个数的最大公因数或最小公倍数，一般都用这两个数除以它们的公因数，一直除到所得的两个商只有公因数1为止。把所有的除数相乘起来，就得到这两个数的最大公因数；把所有的除数和最后的两个商连乘起来，就得到这两个数的最小公倍数。 试一试

用短除法求下列两组数的最大公因数和最小公倍数。 21和28 20和36 练一练 1、根据已知条件求出每组数的最大公因数和最小公倍数。（1）28＝2×2×7 （2）16＝2×2×2×2 35＝5×7 12＝2×2×3 （28,35）＝（）（16,12）＝（） [28,35] ＝（） [16,12] ＝（）2、用适当的方法求下列每组数的最大公因数和最小公倍数。 14和21 20和25 65和52 3、一堆水果糖，分给一个小组的同学们。如果分给男同学，每人5块，结果还剩3块；而分给女同学，每人可以分到8块，结果也还剩3块。问这堆水果糖最少有几块，这一小组有几人？

五年级数学教案《求两个数的最大公约数》

五年级数学教案《求两个数的最大公约数》教学重点理解公约数、最大公约数、互质数的概念。 教学难点理解并掌握求两个数的最大公约数的一般方法。 教学用具投影仪等。 教学过程 一、创设情境 填空：①123=4，所以12能被4（）。4能（）12，12是3的（），3是12的（）。②把18和30分解质因数是，它们公有的质因数是（）。③10的约数有（）。 二、揭示课题 我们已经学会求一个数的约数，现在来看两个数的约数。 三、探索研究 1．小组合作学习 （1）找出8、12的约数来。 （2）观察并回答。 ①有无相同的约数？各是几？

②1、2、4是8和12的什么？ ③其中最大的一个是几？知道叫什么吗？ （3）归纳并板书 ①8和12公有的约数是：1、2、4，其中最大的一个是4。 ②还可以用下图来表示。 813 24612 8和12的公约数 （4）抽象、概括。 ①你能说说什么是公约数、最大公约数吗？ ②指导学生看教材第66页里有关公约数、最大公约数的概念。（5）尝试练习。 做教材第67页上面的做一做的第1题。 2．学习互质数的概念

（1）找出下列各组数的公约数来：5和78和912和251和9 （2）这几组数的公约数有什么特点？ （3）这几组数中的两个数叫做什么？（看书67页） （4）质数和互质数有什么不同？（使学生明确：质数是一个数，而互质数是两个数的关系） 3．学习例2 （1）出示例2并说明：我们通常用分解质因数的方法来求两个数的最大公约数。 （2）复习的第2题，我们已将18和30分解质因数（如后）18=23330=235 （3）观察、分析。 ①从18和30分解质因数的式子中，你能看出18和30各有哪些约数吗？ ②18和30的公约数就必须包含18和30公有的什么？ ③18和30公有的质因数有哪些？

求两个数的最大公约数

求两个数的最大公约数 方法一/最简单的算法(效率最低)，如下: public static int getMaxDivisor(int a, int b) { int max = 0; int temp = Math.min(a, b); for (int i = temp; i > 0; i--) { if (a % i == 0 && b % i == 0) { max = i; break; } } return max;// 当max为0时，即没有最大公约数 } 方法二/代码最少的算法，如下: public static int getMaxDivisor(int a, int b){ if(Math.min(a, b)==0){ return Math.max(a, b); }else{ return getMaxDivisor2(Math.min(a, b), Math.max(a, b)%Math.min(a, b)); } } 方法三/方法二的变换，如下: public static int getMaxDivisor(int a,int b){ int x=a; int y=b; while(Math.min(x,y)!=0){ int temp=y; y=Math.min(x,y); x=Math.max(temp,x)%Math.min(temp,x); if(Math.min(x,y)==0){ return Math.max(x,y); } } return Math.max(a,b); }

—[讨论]求两个数的最大公约数的问题的算法 主题：[讨论]求两个数的最大公约数的问题的算法 小弟是新人,请教各位了,M 和N 的最大公约数的算法是什么呢? 谢了! m和n的最大公约数 int temp, r ,p; if(n < m) { temp = n; n = m; m = temp; } p =n * m; while(m != 0) { r = n % m; n = m; m = r } m是最大公约, p/n是最小公倍 #include "stdafx.h" #include "iostream.h" int main(int argc, char* argv[]) { int m,n; cin>>m>>n; if(m<=n&&n%m==0) cout<<"最大公约数是"<

求最大公约数的原理及算法实现

1.辗转相除法GCD算法的基本原理 DCD - Greatest Common Divisor 欧几里得定理： 若 a = b * r + q，则 GCD(a,b) = GCD(b,q)。 证明： 假设 c = GCD(a,b) 则存在m使得 a = m * c,b = n * c; 因为 a = b * r + q, 则 q = a - b * r = m * c - n * c * r = (m - n * r) * c; 因为 b = n * c , q = (m - n * r) * c 故要证明GCD(a,b) = GCD(b,q)，即证明 n 与 m - n * r互质 下面证明 m-n×r与n互质： 假设不互质，则存在公约数k使得 m - n * r = x * k, n = y * k. 则: a= m * c = (n * r + x * k) * c = (y * k * r + x * k) * c = (y * r + x) * k * c b = n * c = y * c * k 则GCD(a,b) = k * c,与 c=gcd(a, b) 矛盾 2.辗转相除法算法的实现 2.1递归实现

自己改进 2.2迭代实现

3.更相减损法 更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。 《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 翻译成现代语言如下： 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减去小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。 例如：用更相减损术求260和104的最大公约数。 解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。此时65是奇数而26不是奇数，故把65和26辗转相减： 65-26=39 39-26=13 26-13=13 所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即13*2*2=52。2.更相减损法算法的实现 2.1递归实现

求最大公约数和最小公倍数的算法和程序

1.main() 2.{ 3.int p,r,n,m,temp; 4.printf("Please enter 2 numbers n,m:"); 5.scanf("%d,%d",&n,&m);//输入两个正整数. 6.if(n main() { int a,b,x,y; printf("\n *****zui da gong yue shu he zui xiao gong bei shu*****\n"); printf("\nplease input two integer:\n"); scanf("%d,%d",&a,&b); x=f1(a,b); printf("zui da gong yue shu wei:%d\n",x); y=f2(a,b); printf("zui xiao gong bei shu wei:%d\n",y); } int f1(int a,int b)

《找两个数的最大公因数和最小公倍数》教学反思

《找两个数的最大公因数和最小公倍数》教学反思 这节练习课主要教学求两个数的最大公因数和最小公倍数，细细思量，用课本上列举的方法，真的很难一下子准确找到最大公因数和最小公倍数，所以重新归纳了一些特殊情况：1.两个数是倍数关系的，这两个数的最小公倍数是其中较大的数，最大公因数是其中较小的数；2.两个数的公因数是1的情况，最大公因数是1，最小公倍数是他们的乘积。这里有三种情况：（1）两个不同的质数；（2）两个连续的自然数；（3）1和任何自然数。3.一般关系，用大数翻倍的方法去找两个数的最小公倍数。 另外，我有结合教材后面的“你知道吗？”指导了一下用短除法求两个数的最小公倍数和最大公因数的方法。在完成练习时，让学生根据情况，用自己喜欢的方法灵活选择来求两个数的最大公因数和最小公倍数。

小升初数学模拟试卷 一、选择题 1．点A在点C的南偏西32°方向，点B在点C的北偏东75°方向，∠BCA的度数为（） A．75° B．107° C．163° D．137° 2．在一个比例尺是200∶1的图纸上，量得一个零件的长是2厘米，这个零件实际长（）。 A．4米 B．1米 C．0.1毫米 D．0.4毫米 3．下面是甲、乙两个班男、女生人数分布统计图，其中说法正确的是（）。 A．两个班的人数一样多 B．乙班的男生人数比女生多40% C．甲班的女生人数占全班的 D．甲班的女生人数一定比乙班的女生多 4．一个直角三角形的三边分别是6cm、8cm和10cm，这个三角形的面积是（）平方厘米 A．48 B．24 C．60 D．80 5．210＝2×3×5×7，2，3，5，7这四个数都是210的（）。 A．倍数 B．质因数 C．公因数 6．两个高一样的圆锥，他们的底面半径比是3：4，那么它们的体积比是（） A．3：4 B．9：16 C．6：8 D．16：9 7．圆的直径与正方形的边长都是4厘米，那么圆的周长（）正方形的周长。 A．大于B．小于C．等于 8．最小的奇数比最小的合数少（）%． A．75 B．50 C．25 9．两车从甲乙两地同时出发相向而行，相遇时( )。 A．速度相同 B．所行距离相等 C．所用时间相等 10．用一条长200厘米的铁丝围成以下图形，面积最大的是（） A．正方形 B．圆 C．长方形 二、填空题 11．2016年是“十三五”开局之年，这一年的第一季度有________天。 12．根据全国人口普查的最新数据显示，我国2018年全国人口数量为1390080000人，这个数读作（____）人，四舍五入到亿位是（____）亿人． 13．分别用小数、分数、百分数表示下面各直线上的点．(分数，先填分子，后填分母)

【数学】五年级数学教案——《求两个数的最大公约数》教学

---------------------------------------------------------------范文最新推荐------------------------------------------------------ 五年级数学教案——《求两个数的最大公约数》教学 教学要求①使学生理解公约数、最大公约数、互质数的概念。②使学生初步掌握求两个数最大公约数的一般方法。③培养学生抽象、概括的能力和动手实际操作的能力。 教学重点理解公约数、最大公约数、互质数的概念。 教学难点理解并掌握求两个数的最大公约数的一般方法。 教学用具投影仪等。 教学过程 一、创设情境 填空：①12÷3=4，所以12能被4（）。4能（）12，12是3的（），3是12的（）。②把18和30分解质因数是，它们公有 1 / 7

的质因数是（）。③10的约数有（）。 二、揭示课题 我们已经学会求一个数的约数，现在来看两个数的约数。 三、探索研究 1．小组合作学习 （1）找出8、12的约数来。 （2）观察并回答。 ①有无相同的约数？各是几？ ②1、2、4是8和12的什么？ ③其中最大的一个是几？知道叫什么吗？ （3）归纳并板书

---------------------------------------------------------------范文最新推荐------------------------------------------------------ ①8和12公有的约数是：1、2、4，其中最大的一个是4。 ②还可以用下图来表示。 813 24612 8和12的公约数 （4）抽象、概括。 ①你能说说什么是公约数、最大公约数吗？ ②指导学生看教材第66页里有关公约数、最大公约数的概念。 （5）尝试练习。 做教材第67页上面的做一做的第1题。 2．学习互质数的概念 3 / 7