- 浏览: 990742 次
- 性别:
- 来自: 广州
文章分类
- 全部博客 (1355)
- test (75)
- 红茶和绿茶 (1)
- Jave SE (206)
- Oracle (19)
- English (177)
- Log4j (5)
- RIA(Rich Internet Applications) (9)
- Ext Js (6)
- Android (14)
- Logo (0)
- 文字采撷 (287)
- 使用技巧 (92)
- Project Management (22)
- Hibernate (12)
- Struts (5)
- 规则引擎 (1)
- Html & Javasctipt (56)
- Spring MVC (10)
- Maven (17)
- Java Test (17)
- Linux (16)
- Tools (1)
- CV (0)
- Middleware (2)
- HTML5 (2)
- Algorithms (4)
- Web Service (15)
- 留学 (15)
- LADP (5)
- PXCOA (0)
- SysLog (6)
- SSO (3)
- Spring Security (4)
- Spring Batch (1)
- Jmail (1)
- Bible (4)
- Java Thread (5)
- Architect (6)
- github (2)
- Java Swing (12)
- NoSQL (7)
- UML (2)
- 敏捷(Agile) (7)
- Hudson+Maven+SVN (15)
- cloud computing (2)
- Bahasa Indonesia (1)
- jBPM (6)
- 民俗知识 (3)
- Consulting (1)
- Mysql (5)
- SAP (1)
- 微信公众平台接口开发 (3)
- 做生意 (1)
- 西餐 (1)
- Banking (1)
- Flex (0)
- 黄金投资 (1)
- Apache Tomcat 集群 (3)
- Hadoop (7)
- 需求分析 (1)
- 银行知识 (3)
- 产品管理 (2)
- 钢琴Music (3)
- 设计 (3)
- Marketing (2)
- US Life (3)
- 算法 (14)
- BigData (4)
- test红茶和绿茶Jave SEOracleEnglishLog4jRIA(Rich Internet Applications)Ext JsAndroidLogo文字采撷 (0)
- Design Pattern (5)
- NodeJS&AngularJS (9)
- Python (1)
- Spring boot (0)
- ACM (3)
最新评论
-
心往圣城:
微时代-最专业的微信第三方平台。LBS定位导航,微网站,自定义 ...
微信公众平台 /微信公众平台怎么用 -
zhaojiafan:
return ReverseStr1(str.substrin ...
逆转字符串 Write a String Reverser (and use Recursion!) -
zhaojiafan:
public class StringUtils {
p ...
逆转字符串 Write a String Reverser (and use Recursion!)
如果数a能被数b整除,a就叫做b的倍数,b就叫做作a的约数.约数和倍数都表示一个数与另一个数的关系,不能单独存在.如只能说16是某数的倍数,2是某数的约数,而不能孤立地说16是倍数,2是约数.
“倍”与“倍数”是不同的两个概念,“倍”是指两个数相除的商,它可以是整数、小数或者分数.“倍数”只是在数的整除范围内,相对于“约数”而言的一个数字概念,表示的是能被某一个自然数整除的数,它必须是一个自然数.
(1)最大公约数
最大公约数:几个自然数公有的约数,叫做这几个数的公约数;其中最大的一个,叫做这几个数的最大公约数。
例如:12,16的公约数有1,2,4,其中最大的一个是4,4是12与16的最大公约数,一般记为(12,16)=4.12,15,18的最大公约数是3,记为(12,15,18)=3.
常用的求最大公约数的方法是短除法和分解质因数法.
短除法:开始时用观察比较的方法,即:先把每个数的约数找出来,然后再找出公约数,最后在公约数中找出最大公约数。
例如:求12与18的最大公约数。
短除法例题
12的约数有:1、2、3、4、6、12。
18的约数有:1、2、3、6、9、18。
12与18的公约数有:1、2、3、6。
12与18的最大公约数是6。
这种方法对求两个以上数的最大公约数,特别是数目较大的数,显然是不方便的。于是又采用了给每个数分别分解质因数的方法。
分解质因数法:把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数.例如,求24和60的最大公约数.24=2×2×2×3,60=2×2×3×5,24与60的全部公有的质因数是2,2和3,它们的积是2×2×3=12,所以(24,60)=12.
除了这两种方法外,还有一种辗转相除法:
在数学中,辗转相除法,又称欧几里得算法,是求最大公约数的算法。
两个数求最大公约数,可以用辗转相除法。始终用较大数(被除数)除以较小数(除数),然后用除数代替较大数(被除数),余数代替较小数(除数),代替完后继续让新的被除数除以除数。直到相除余数为0时。最后的除数就是最大公约数。举例:
222 407求最大公约数:
222 407(407除以222余数185)
222 185(222除以185余数37)
37 185(185除以37余数0)
所以最大公约数为37
39 24求最大公约数
39 24(39/24,余数15)
15 24(24/15,余数9)
15 9(15/9,余数6)
6 9(9/6,余数3)
6 3(6/3,余数0)
所以最大公约数为3
辗转相除法可以用来计算两个自然数的最大公约数,那若要计算多个自然数的最大公约数呢?
答:求几个自然数的最大公约数,可以先求出其中两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个为止。最后所得的那个最大公约数,就是所求的几个数的最大公约数。(求多个数的最小公倍数时也是同样的道理)
(2)最小公倍数
最小公倍数:几个数公有的倍数叫做这几个数的公倍数,其中最小的一个叫做这几个数的最小公倍数。数学上常用方括号表示。如[12,18,20]即12、18和20的最小公倍数。
最小公倍数的求法:
求几个自然数的最小公倍数,同样也可以采用分解质因数法和短除法
<1> 分解质因数法:先把这几个数分解质因数,再把它们一切公有的质因数和其中几个数公有的质因数以及每个数的独有的质因数全部连乘起来,所得的积就是它们的最小公倍数。
例如,求[12,18,20],因为12=2^2×3,18=2×3^2,20=2^2×5,其中三个数的公有的质因数为2,两个数的公有质因数为2与3,每个数独有的质因数为5与3,所以,[12,18,20]=2^2×3^2×5=180。
<2> 短除法:
其实只要求出了最大公约数就能直接求最小公倍数了。可利用下面这条公式
两个数相乘等于这两个数的最大公约数和最小公倍数的积。
java案例:
《1》求两个数的最大公约数和最小公倍数(杭电ACM--1108有类似的题)
解法:用辗转相除法先求出最大公约数,再通过公式:两个数相乘等于这两个数的最大公约数和最小公倍数的积。求出最小公倍数
代码如下:
import java.util.Scanner;
public class Test1018 {
//求最大公约数
public static int commonDivisor(int n,int m){
//辗转相除是用大的除以小的。如果n<m,第一次相当n与m值交换
while(n%m!=0){
int temp=n%m;
n=m;
m=temp;
}
return m;
}
//求最小公倍数
public static int commonMultiple(int n,int m){
return n*m/commonDivisor(n,m);
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
System.out.println(commonMultiple(n,m));
System.out.println(commonDivisor(n,m));
}
}
《2》根据用户输入的个数,求出这些数的最小公倍数,以杭电ACM--2028为例
Lowest Common Multiple Plus
public class Test2028 {
//求两个最大公约数
public static long commonDivisor(long n,long m){
//辗转相除是用大的除以小的。如果n<m,第一次相当n与m值交换
while(n%m!=0){
long temp=n%m;
n=m;
m=temp;
}
return m;
}
//求两个数最小公倍数
public static long commonMultiple(long n,long m){
return n*m/commonDivisor(n,m);
}
//求多个数的最小公倍数
public static long commonMultiple(long[] a){
long value=a[0];
for(int i=1;i<a.length;i++){
value=commonMultiple(value,a[i]);
}
return value;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
long[] a=new long[n];
for(int i=0;i<a.length;i++){
a[i]=sc.nextLong();
}
System.out.println(commonMultiple(a));
}
}
发表评论
-
各种在线工具
2018-05-10 05:52 375http://rextester.com/ -
Java Array sort and Collections sort
2018-04-11 04:55 343package com.test; imp ... -
webpack+es6+node+react初实践及总结
2018-02-01 10:38 319webpack+es6+node+react初实践及总结 ... -
Interview Preparation
2018-01-25 08:26 396Algorithms https://www. ... -
深入理解Java集合框架
2017-08-18 08:40 573https://github.com/CarpenterLe ... -
logic gate (AND, OR, XOR, NOT, NAND, NOR and XNOR)
2017-08-18 08:33 2349A logic gate is an elementary ... -
深入理解Java PriorityQueue
2017-08-18 01:25 382本文github地址 Java中PriorityQueu ... -
jwt-spring-security-demo
2017-08-12 07:30 546https://github.com/szerh ... -
Java Program to Check Whether a Number is Palindrome or Not
2017-08-08 06:59 497public class Palindrome { ... -
Java实现Tire
2017-08-07 08:14 546Java实现Tire Trie ... -
OpenID, SAML, and OAuth
2017-08-03 07:03 546Single sign-on (SSO) started i ... -
分享两个JavaEE 非常好的网站,案例丰富
2017-08-01 09:07 293http://www.mkyong.com/al ... -
Introduction to Programming in Java
2017-07-19 13:26 412http://introcs.cs.princeton.ed ... -
Two piece of code
2017-06-20 00:43 388if ( updateRe ... -
ACM Online Judge
2017-06-05 01:26 414http://acm.nyist. ... -
java枚举使用详解
2017-05-25 06:16 420package com.ljq.test; /** ... -
Longest Common Substring
2017-05-21 08:22 462Dynamic Programming | Set 29 ( ... -
Dynamic Programming
2017-05-06 10:48 325Dynamic Programming | Set 1 (O ... -
Predefined Character Classes
2017-04-24 02:45 362Predefined Character Clas ... -
IS-A Relationship And HAS-A Relationship
2017-04-13 14:50 1084One of the advantages of an Ob ...
相关推荐
Java求最大公约数、最小公倍数,输入两个正整数m和n,求其最大公约数和最小公倍数。最小公倍数可由原数除以最大公约数计算得到,这里使用了辗除法。
JAVA实现求最大公约数和最小公倍数 根据欧几里得定律,最大公约数的递归算法
求最大公约数和最小公倍数的快速方法(Java语言实现)。
最大公约数、最小公倍数 * 最大公约数(a,b) * 12的因数:1、2、3、4、6、12 * 18的因数:1、2、3、6、9、18 * 12和18的最大公约数... * 两个数的积等于这两个数的的最大公约数与最小公倍数的积。即(a,b)*[a,b]=a*b
最大公约数与最小公倍数的求法。简单明了,通俗易懂,是不错的算法
用碾压法求出两个数的最大公因数,然后将剩下的分子连乘再乘以最大公因数即可获得最小公倍数
Java练习题:输入两个正整数m和n,求其最大公因数和最小公倍数
java 最大公约数与最小公倍数代码 使用的for 方法
求其最大公约数和最小公倍数输入两个正整数m和n,求其最大公约数和最小公倍数输入两个正整数m和n,求其最大公约数和最小公倍数输入两个正整数m和n,求其最大公约数和最小公倍数输入两个正整数m和n,求其最大公约数和...
用java写的小程序,输入两个数,求得他们的最大公约数和最小公倍数
java代码-使用java求最大公约数和最小公倍数的源代码 ——学习参考资料:仅用于个人学习使用!
很简单明了的一个小java代码,帮助初学者进行学习
1. Java不同数据类型变量的使用 ①定义不同的字符变量,依次给这些变量赋值:’A’,’2’,’猫’,’b’并输出结果;...2. 计算最小公倍数和最大公约数 ①定义两个整型变量m,n; ②计算最大公约数; ③最小公倍数;
使用java语言实现输入两个数字对齐进行计算,并输出它两个的最大公约数和最小公倍数。
主要介绍了java求最大公约数与最小公倍数的方法,涉及java数值运算的相关操作技巧,并附带分析了eclipse环境下设置运行输入参数的相关操作技巧,需要的朋友可以参考下
java 辗转相除法 求两个数的最小公倍数 求三个数的最大公约数
用JAVA写了个关于两个数最大公约数最小公倍数的程序..不晓得质量如何import java.util.*; public class dd { public static void main(String args[]){ Scanner scanner; scanner=new Scanner(System.in); int m...
int b),该方法返回a和b的最大公约数,然后再编写一个该类的子类,要求子类重写方法f,而且重写的方法将返回a和b的最小公倍数,要求在重写的方法的方法体中首先调用被隐藏的方法返回a和b的最大公约数m,然后将乘积(a*b...
java算法最大公约数和最小公倍数.pdf
java实现计算最大公约数最小公倍数