C語言求最大公約數和最小公倍數的幾種算法

求最小公倍數算法

最小公倍數=兩整數的乘積÷最大公約數

求最大公約數算法

(1)輾轉相除法

有兩整數ab

①?a%b得余數c

②?c=0,則b即為兩數的最大公約數

③ 若c≠0,則a=bb=c,再回去執行①

例如求2715的最大公約數過程為:

27÷15?1215÷12312÷30因此,3即為最大公約數

?

[cpp]?view plain?copy

  1. #include<stdio.h>??
  2. void?main()???/*??輾轉相除法求最大公約數?*/???
  3. {???
  4. ???int?m,?n,?a,?b,?t,?c;??
  5. ???printf("Input?two?integer?numbers:\n");??
  6. ???scanf("%d%d",?&a,?&b);??
  7. ???m=a;???n=b;??
  8. ???while(b!=0)??/*?余數不為0,繼續相除,直到余數為0?*/???
  9. ???{?c=a%b;?a=b;??b=c;}??
  10. ???printf("The?largest?common?divisor:%d\n",?a);??
  11. ???printf("The?least?common?multiple:%d\n",?m*n/a);??
  12. }??

?

⑵ 相減法

有兩整數a和b:

① 若a>b,則a=a-b

② 若a<b,則b=b-a

③ 若a=b,則a(或b)即為兩數的最大公約數

④ 若a≠b,則再回去執行①

例如求27和15的最大公約數過程為:

27-15=12( 15>12 ) 15-12=3( 12>3 )

12-3=9( 9>3 ) 9-3=6( 6>3 )

6-3=3( 3==3 )

因此,3即為最大公約數

?

[cpp]?view plain?copy

  1. #include<stdio.h>??
  2. void?main?(?)??/*?相減法求最大公約數?*/??
  3. {????
  4. ???int?m,?n,?a,?b,?c;??
  5. ?? ?printf("Input?two?integer?numbers:\n");??
  6. ???scanf?("%d,%d",?&a,?&b); m=a;?n=b;???
  7. ?????/*?a,?b不相等,大數減小數,直到相等為止。*/? ??
  8. ???while?(?a!=b)???
  9. ?????????if?(a>b)??a=a-b; ???????
  10. ?????????else??b=b-a; ??
  11. ???printf("The?largest?common?divisor:%d\n",?a);??
  12. ???printf("The?least?common?multiple:%d\n",?m*n/a);??
  13. }??

?

?

?

⑶窮舉法

有兩整數a和b:

① i=1

② 若a,b能同時被i整除,則t=i

③ i++

④ 若 i <= a(或b),則再回去執行②

⑤ 若 i > a(或b),則t即為最大公約數,結束

改進:

① i= a(或b)

② 若a,b能同時被i整除,則i即為最大公約數,

結束

③ i--,再回去執行②

有兩整數a和b:

① i=1

② 若a,b能同時被i整除,則t=i

③ i++

④ 若 i <= a(或b),則再回去執行②

⑤ 若 i > a(或b),則t即為最大公約數,結束

改進:

① i= a(或b)

② 若a,b能同時被i整除,則i即為最大公約數,

結束

③ i--,再回去執行②

?

[cpp]?view plain?copy

  1. #include<stdio.h>??
  2. void?main?()??/*?窮舉法求最大公約數?*/??
  3. {????
  4. ???int??m,?n,?a,?b,?i,?t; ??
  5. ???printf("Input?two?integer?numbers:\n");??
  6. ???scanf?("%d,%d",?&a,?&b); m=a;??n=b;???
  7. ???for?(i=1;?i<=?a;?i++)????
  8. ???????if?(?a%i?==?0?&&?b%i?==0?)????t=i;??
  9. ???printf("The?largest?common?divisor:%d\n",?t);??
  10. ???printf("The?least?common?multiple:%d\n",?m*n/t);??
  11. }???
  12. /*??改進后的?
  13. ???for?(t=?a;?t>0;?t--?)?????
  14. ???????if?(?a%t?==?0?&&?b%t?==0?)????break;??
  15. */??

?

[cpp]?view plain?copy

  1. //窮舉法求最小公倍數??
  2. ?????for?(i=?a;?;?i++?)??
  3. ?????????if?(?i?%?a?==?0?&&?i?%?b?==0?)?????break;??
  4. ?????printf("The?least?common?multiple:%d\n",?i?)??
  5. ???
  6. //多個數的最大公約數和最小公倍數??
  7. ?????for?(i=?a;?i>0;?i--?)??
  8. ?????????if?(a%i==0&&b%i==0&&c%i==0)?????break;??
  9. ?????printf("The?largest?common?divisor:%d\n",?i);??
  10. ?????for?(i=?a;?;?i++?)??
  11. ?????????if?(i%a==0&&i%b==0&&i%?c==0)????break;??
  12. ?????printf("The?least?common?multiple:%d\n",?i?)??
  13. ?

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/456986.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/456986.shtml
英文地址,請注明出處:http://en.pswp.cn/news/456986.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

3月15日云棲精選夜讀:雙管齊下,MaxCompute數據上云與生態

雙管齊下&#xff0c;MaxCompute數據上云與生態 作者&#xff1a;場景研讀 Go語言并發機制初探 作者&#xff1a;邴越 趣拍云短視頻SDK全面升級&#xff0c;簡單易用引開發者點贊 作者&#xff1a;sherry是雪梨 發表在&#xff1a;趣拍云團隊 阿里云機器學習平臺編程模型演…

qt android glsl,基于Qt的OpenGL學習(1)—— Hello Triangle

簡介要學習OpenGL的話&#xff0c;強烈安利這個教程JoeyDeVries的learnopengl&#xff0c;這里是中文翻譯好的版本。教程中使用OpenGL是通過GLFW這個庫&#xff0c;而在Qt中對OpenGL封裝得很好&#xff0c;并且和GUI以及IO相關的處理Qt更便捷&#xff0c;學習起來更輕松。這里就…

解決:Not Found: /favicon.ico

直接說解決辦法&#xff1a; &#xff08;1&#xff09;制作一個 favicon.ico圖標放在<head></head>標簽中 <link rel"shortcut icon" href"xxxxxxxxxx.ico" type"image/x-icon" /> <!--制作的圖標&#xff0c;使用hr…

多態方法調用的解析和分派

方法調用并不等同于方法執行&#xff0c;方法調用階段唯一的任務就是確定被調用方法的版本&#xff08;即調用哪一個方法&#xff09;&#xff0c;暫時還不涉及方法內部的具體運行過程。在程序運行時&#xff0c;進行方法調用是最普遍、最頻繁的操作&#xff0c;Class文件的編譯…

ES6:Set和Map

Set Set:類似數組&#xff0c;但是成員的值都是唯一的&#xff0c;沒有重復。Set本身是一個構造函數&#xff0c;用來生成Set數據結構。他包含的方法&#xff1a;add: 添加某個值&#xff0c;返回Set結構本身。delete: 刪除某個值&#xff0c;返回一個布爾值&#xff0c;表示是…

九九乘法表[循環嵌套]

#九九乘法表 # 1*11 # 1*22 2*24 # 1*33 2*36 3*39 # ...#循環嵌套 #行數 i 1 while i < 9:# 打印每行的內容j 1while j < i:print("%d * %d %3d " % (i, j, i * j), end)j 1print() # 換行i 1while嵌套&#xff1a;w 1 while w < 10: #外層循…

關于用VS寫C程序運行時出現燙字以及亂碼的問題的原因

最近在復習C語言寫程序時&#xff0c;突然碰到標題上的這種情況&#xff0c;后來經過上網查找以及逐步調試才發現原來是在打印數組的時候“越界”導致的&#xff0c;因為程序在默認初始化char類型的數組時&#xff0c;初始化的值是“燙”字&#xff0c;一般情況下是字符串未初始…

javascript函數調用的各種方法!!

在JavaScript中一共有下面4種調用方式&#xff1a; (1) 基本函數調用 (2)方法調用 (3)構造器調用 (4)通過call()和apply()進行調用 1. 基本函數調用 普通函數調用模式&#xff0c;如&#xff1a; JavaScript code?1234function fn(o){…… }fn({x:1});在基本函數調用中&#x…

ARM TK1 安裝kinect驅動

首先安裝usb庫 $ git clone https://github.com/libusb/libusb.git 編譯libusb需要的工具 $ sudo apt-get install autoconf autogen $ sudo apt-get install libtool $ sudo apt-get install libudev* 編譯安裝 $ sudo ./autogen.sh $ sudo make $ sudo make install $ sudo l…

如何在一個html頁面中提交兩個post,如何在同一個頁面上從Django和Ajax獲得多個post請求?...

我一整天都在為這事犯愁。似乎什么都沒用。這是我的情況。在我有一個Django表單&#xff0c;有兩個字段&#xff1a;redirect_from&#xff0c;redirect_to。此表單有兩個提交按鈕&#xff1a;Validate和{}。當頁面加載時&#xff0c;Submit被隱藏&#xff0c;只顯示Validate。…

大數據入門:各種大數據技術的介紹

大數據我們都知道hadoop&#xff0c;可是還會各種各樣的技術進入我們的視野&#xff1a;Spark&#xff0c;Storm&#xff0c;impala&#xff0c;讓我們都反映不過來。為了能夠更好的架構大數據項目&#xff0c;這里整理一下&#xff0c;供技術人員&#xff0c;項目經理&#xf…

高可用與負載均衡(5)之基于客戶端的負載均衡

什么是客戶端負載均衡 基于客戶端的負載均衡&#xff0c;簡單的說就是在客戶端程序里面&#xff0c;自己設定一個調度算法&#xff0c;在向服務器發起請求的時候&#xff0c;先執行調度算法計算出向哪臺服務器發起請求&#xff0c;然后再發起請求給服務器。 基于客戶端負載均衡…

Variant 與 內存泄露

http://blog.chinaunix.net/uid-10386087-id-2959221.html 今天遇到一個內存泄露的問題。是師兄檢測出來的。Variant類型在使用后要Clear否則會造成內存泄露&#xff0c;為什么呢&#xff1f; Google一下找到下面一篇文章&#xff0c;主要介紹了Com的內存泄露&#xff0c;中間有…

安裝安全類軟件進行了android簽名漏洞修補,魅族MX3怎么升級固件體驗最新比較穩定的版本...

魅族mx3固件怎么升級?flyme os系統會持續更新&#xff0c;升級魅族MX3手機系統需先下載MX3的升級固件&#xff0c;升級固件分為體驗版和穩定版。魅族MX3固件有體驗版和穩定版兩種&#xff0c;顧名思義&#xff0c;體驗版為最新版但相比穩定版來說存在更多的漏洞&#xff0c;升…

linux su切換用戶提示Authentication failture的解決辦法

由于ubtun系統默認是沒有激活root用戶的&#xff0c;需要我們手工進行操作&#xff0c;在命令行界面下&#xff0c;或者在終端中輸入如下命令&#xff1a; sudo passwd Password&#xff1a;你當前的密碼 Enter new UNIX password&#xff1a;這個是root的密碼 Retype new …

@property

class Person(object):def __init__(self, name,age):#屬性直接對外暴露#self.age age#限制訪問self.__age ageself.__name namedef getAge(self):return self.__agedef setAge(self,age):if age<0:age 0self.__age age#方法名為受限制的變量去掉雙下劃線propertydef a…

ubuntu入門知識

1、linux系統發展歷史 unix -> Linux -> ubuntu linux發展軌跡圖 2、ubuntu下載和安裝 推薦使用長期支持版本&#xff1a; 10.04,12.04,14.04或LTS版本 安裝環境VMware虛擬機 3、安裝之后創建root sudo passwd root 輸入root用戶密碼即可 4、安裝軟件&#xff1a; 更新軟…

html 二級試題,計算機二級考試WEB試題及答案

計算機二級考試WEB試題及答案當前主要的 WEB數據庫訪問技術有哪些?答&#xff1a;到目前為止&#xff0c;WEB數據庫訪問技術主要分為兩大類&#xff1a;(1)公共網關接口技術(CGI);CGI 是 WEB 服務器運行時外部程序的規范&#xff0c;按照 CGI 編寫的程序可以擴展服務器的功能&…

細數阿里云服務器的十二種典型應用場景

原文鏈接&#xff1a;http://click.aliyun.com/m/13910/免費開通大數據服務&#xff1a;https://www.aliyun.com/product/odps文章轉載&#xff1a;小白楊1990如今&#xff0c;阿里云的產品可謂是多種多樣&#xff0c;紛繁復雜。面對各種各樣的技術和產品&#xff0c;ECS、RDS、…

動態給實例添加屬性和方法

from types import MethodType#創建一個空類 class Person(object):__slots__ ("name","age","speak","height")per Person() #動態添加屬性&#xff0c;這體現了動態語言的特點(靈活&#xff09;per.name "tom" print(…