求两个自然数的最大公约数有哪些方法

1、质因数分解:

把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数。

2、短除法:

短除法求最大公约数,先用这几个数的公约数连续去除,一直除到所有的商互质为止,然后把所有的除数连乘起来,所得的积就是这几个数的最大公约数。

3、辗转相除法:

辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。这就是辗转相除法的原理。用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。最后所得的那个最大公约数,就是所有这些数的最大公约数。

4、更相减损法:

也叫更相减损术,是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”

翻译成现代语言如下:

第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。

第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

转载请注明出处育才学习网 » 求两个自然数的最大公约数有哪些方法

知识

剪贴板的功能是什么

阅读(219)

剪贴板是Windows系统一段可连续的,可随存放信息的大小而变化的内存空间。功能:可临时保存剪切和复制的信息,且可以存放的信息种类是多种多样的。注意:剪切或复制时保存在剪贴板上的信息,只有再剪贴或复制另外的信息,或停电、或退出windows、或

知识

有哲理的QQ个性签名

阅读(204)

以下是有哲理的QQ个性签名收录:1.暗恋,就是一个人写两个人的故事。2.岁月是一个封闭的容器,没有人能看懂也看不清。3.生活不易,全靠演技。把角色演成自己,把自己演到失忆。4.当你让痛苦停泊时,幸福就会在别处靠岸。5.前面就是路,要适应着独自去

知识

2017顺丰快递收费标准

阅读(403)

1.广东省内,首重每千克十二元、续重每千克两元;2.江苏、浙江、上海、北京、福建,首重每千克二十元、续重每千克十三元;3.天津、重庆、安徽、广西、贵州、海南、河北、河南、湖北、湖南、江西、山东、山西、陕西、四川、云南、首重每千克二十

知识

“爱”的同义字有什么啊

阅读(397)

有惜、好、慕、喜、悦。解释如下:惜:意为爱,重视;爱惜、顾惜、珍惜。好:意为喜欢;好客,好斗。慕:意为依恋,向往,敬仰;爱慕,钦慕。喜:意为爱好;喜欢。悦:意为喜,喜欢;士为知己者用,女为悦己者容。

知识

搞软件开发的可以考什么职业资格证书

阅读(275)

搞软件开发可以考的职业资格证书:计算机技术与软件专业技术资格。计算机技术与软件专业技术资格考试是原中国计算机软件专业技术资格和水平考试的完善与发展。这是由国家人力资源和社会保障部、工业和信息化部领导的国家级考试,其目的是,科

知识

高职与中专的区别主要

阅读(235)

高职与中专的区别如下:高等职业教育,在中国大陆地区,高等职业教育包括专科和本科两个学历教育层次,高职学生毕业时颁发国家承认学历的普通高等学校专科和本科毕业证书,并享受普通高校毕业生的一切待遇。高职特征:使学生具备必要理论知识和科学

知识

唬人、点睛之笔是什么意思

阅读(211)

唬人的意思为通过某种方式欺骗、吓唬别人。点睛之笔:1.释义:笔,文笔,指文章传神绝妙之处。2.出处:《晋书顾恺之传》:“恺之每画人成,或数年不点目睛。人问其故。答曰:四体妍蚩,本无阙少于妙处,传神写照,正在阿睹中”。3.近义词:画龙点睛。4.例句:百花

知识

职工福利费工会经费和职工教育经费的税前扣除标准是多少

阅读(229)

三者的税前扣除标准分别是:1.职工福利费是工资薪金总额的14%;2.工会经费是工资薪金总额的2%;3.职工教育经费是工资薪金总额的2.5%,在职工教育经费方面,为鼓励企业加强职工教育投入,《企业所得税实施条例》规定,除国务院财税主管部门另有规定外,

知识

自考可可以直接考本科吗

阅读(233)

因为考生办理本科毕业证书时,必须交验国家承认学历的专科及以上学历证书原件,所以无专科学历的不可直接报考本科,但专科在读生也可报考本科,需在领本科毕业证时,有国民教育系列的专科毕业证。自考本科报考基本条件:是中华人民共和国公民,不受性

知识

厦门哪家老婆饼比较好吃亲们推荐一下吧

阅读(358)

1.宝岛太阳堂饼铺:位于福建省厦门市思明区莲花北路3号之1杠9太阳堂。2.义兰中糖饼店:位于福建省厦门市思明区禾祥东路益城广场12之36店面。3.安德鲁森碧湖嘉园店:位于福建省厦门市湖里区枋湖东二里3号之6店面。4.澳联西饼金鸡亭店:位于福建

知识

关于哈尔滨工业大学图书馆

阅读(219)

哈尔滨工业大学图书馆建于1920年。图书馆是全校文献信息资源中心,设有七个业务部室及办公室,为读者提供文献借阅和信息服务。目前,哈工大图书馆是教育部CALIS东北国防文献信息中心,教育部CALIS数字图书馆基地,黑龙江省高校图工委秘书处所在馆

知识

狗狗的叫声像哭一样是怎么回事

阅读(541)

狗狗叫声像哭一样不会是生病导致的,狗狗生病会很没精神,所以不用担心狗狗是否生病。狗狗有时候叫声就像在哭,尤其是刚到一个新环境,那是因为它感到害怕,没有安全感,如果能给它安全感,多和它亲近,别冷落它,给他足够的食物和水,睡觉的时候,把它的狗窝

知识

为什么要使用蓝光钓鱼灯有什么好处

阅读(386)

一、使用蓝光钓鱼灯的理由与好处有以下五点:1.蓝光钓鱼灯可以有效反射浮漂荧光,使之清晰可见。2.蓝光因为波长原因,不会惊扰鱼群。3.长时间盯视无疲惫感。4.特殊光色可吸引鱼群趋光聚集,使夜钓效果更佳。5.蓝色灯光对人体无害,紫光对人体有害

知识

2017东京乒乓球世锦赛决塞时间

阅读(234)

2017年6月8日东京乒乓球世锦赛决塞开始举行,中国队拿到两项单打冠军实现包揽。马龙再次战胜樊振东赢得男单冠军,16岁的孙颖莎在1比3落后时连扳三局逆转击败陈梦夺得女单冠军。马龙和孙颖莎在本次赛事都成为双冠王,中国队包揽全部四项冠军。

知识

哪个师傅可以告诉我一下猪肠粉酱汁的调制方法要比较简单的

阅读(291)

材料:鱼露45毫升,米酒30毫升,芝麻油15毫升,白糖50克,碎大蒜8克,或适量,生姜末10克,蜂蜜30毫升。做法:1.将鱼露、米酒、芝麻油、白糖、大蒜、生姜、蜂蜜放入一小碗里用力搅拌至混匀即可;2.将选用的肉类浸泡在腌汁里至少6小时或在要吃的前一天腌上即

知识

测量按测量方式分类和按测量方法分类分别可分为哪些

阅读(293)

按测量方式分类可以分为直接测量、间接测量和组合测量三类,按测量方法分类可以分为,绝对测量和相对测量、接触测量和非接触测量、单项测量和综合测量、自动测量和非自动测量、静态测量和动态测量、主动测量和被动测量六种。其中直接测量法

知识

猕猴桃酒的家庭制作方法

阅读(268)

家庭制作猕猴桃酒所需材料:猕猴桃、高度白酒、酵母糖液、白砂糖、密封容器、纱布。制作方法:1.将猕猴桃漂洗,去杂质;2.将清洗干净的猕猴桃放入容器中,用木棒捣碎成果浆;3.将果浆倒入干净密封容器,加入5%的酵母糖液搅拌均匀进行前发酵,温度控制在

知识

玻璃海棠的扦插和养殖方法和注意事项

阅读(222)

方法:扦插繁殖全年均可进行,但以春、秋季为最好,一般选取8到10厘米带顶梢的枝条,插于沙床内,保持湿润,约3周左右即可生根,也可进行水插,播种繁殖于4-5月在室内进行盆播,保持室温20℃,约1周左右即可生根,苗高3cm左右时即可上盆。注意事项:1.须根发达

知识

双踪示波器的使用方法

阅读(353)

双踪示波器的使用方法如下:1.选择Y轴耦合方式:根据被测信号频率的高低,将Y轴输入耦合方式选择“AC至DC”开关置于AC或DC;2.选择Y轴灵敏度:根据被测信号的大约峰至峰值,将Y轴灵敏度选择div开关或Y轴衰减开关,置于适当档级。实际使用中如不需读测

知识

红头k果实的功能和食用方法

阅读(313)

1.功能:花含有丰富的维生素C,有清凉降火、生津止渴的功效。花萼与种子油,对心血管、动脉硬化、高血压、骨折、儿童发育不良、老年消化不良、胃酸缺乏等症均有疗效。2.食用方法:花萼可制蜜饯、果酱、高级饮料、冷饮、汽水、冰茶、热茶、冰榨

知识

带有两个不字的四字词语

阅读(436)

1、不卑不亢:卑,低、自卑;亢,高傲。指对人有恰当的分寸,既不低声下气,也不傲慢自大。2、不瞅不睬:不看也不答理。形容待人态度冷淡。3、不揪不睬:指不理睬。4、不偢不倸:犹不理不睬;指一切事情都不注意。5、不茶不饭:不思饮食。形容心事重重。6、不

知识

流体力学的研究方法有哪些各有何特点

阅读(339)

1.现场观测对自然界固有的流动现象或已有工程的全尺寸流动现象,利用各种仪器进行系统观测,从而总结出流体运动的规律并借以预测流动现象的演变。2.实验室模拟在实验室内,人们也可以造成自然界很少遇到的特殊情况,可以使原来无法看到的现象显

[/e:loop]