用java编写程序,输入两个正整数,利用辗转相除法求两个整数的最大公约数和最小公倍数
输入两个正整数m和n, 求其最大公约数和最小公倍数.
用辗转相除法求最大公约数
算法描述:
m对n求余为a, 若a不等于0
则 m <- n, n <- a, 继续求余
否则 n 为最大公约数
最小公倍数 = 两个数的积 / 最大公约数
#include
int main()
{
int m, n;
int m_cup, n_cup, res; /*被除数, 除数, 余数*/
printf("Enter two integer:
");
scanf("%d %d", &m, &n);
if (m > 0 && n >0)
{
m_cup = m;
n_cup = n;
res = m_cup % n_cup;
while (res != 0)
{
m_cup = n_cup;
n_cup = res;
res = m_cup % n_cup;
}
printf("Greatest common divisor: %d
", n_cup);
printf("Lease common multiple : %d
", m * n / n_cup);
}
else printf("Error!
");
return 0;
}
★ 关于辗转相除法, 搜了一下, 在我国古代的《九章算术》中就有记载,现摘录如下:
约分术曰:“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”
其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法,实际上就是辗转相除法。
辗转相除法求最大公约数,是一种比较好的方法,比较快。
对于52317和75569两个数,你能迅速地求出它们的最大公约数吗?一般来说你会找一找公共的使因子,这题可麻烦了,不好找,质因子大。
现在教你用辗转相除法来求最大公约数。
先用较大的75569除以52317,得商1,余数23252,再以52317除以23252,得商2,余数是5813,再用23252做被除数,5813做除数,正好除尽得商数4。这样5813就是75569和52317的最大公约数。你要是用分解使因数的办法,肯定找不到。
那么,这辗转相除法为什么能得到最大公约数呢?下面我就给大伙谈谈。
比如说有要求a、b两个整数的最大公约数,a>b,那么我们先用a除以b,得到商8,余数r1:a÷b=q1…r1我们当然也可以把上面这个式子改写成乘法式:a=bq1+r1------l)
如果r1=0,那么b就是a、b的最大公约数3。要是r1≠0,就继续除,用b除以r1,我们也可以有和上面一样的式子:
b=r1q2+r2-------2)
如果余数r2=0,那么r1就是所求的最大公约数3。为什么呢?因为如果2)式变成了b=r1q2,那么b1r1的公约数就一定是a1b的公约数。这是因为一个数能同时除尽b和r1,那么由l)式,就一定能整除a,从而也是a1b的公约数。
反过来,如果一个数d,能同时整除a1b,那么由1)式,也一定能整除r1,从而也有d是b1r1的公约数。
这样,a和b的公约数与b和r1的公约数完全一样,那么这两对的最大公约数也一定相同。那b1r1的最大公约数,在r1=0时,不就是r1吗?所以a和b的最大公约数也是r1了。
有人会说,那r2不等于0怎么办?那当然是继续往下做,用r1除以r2,……直到余数为零为止。
在这种方法里,先做除数的,后一步就成了被除数,这就是辗转相除法名字的来历吧。
public class test { public static void main(String[] args) { // TODO Auto-generated method stub int res = gcd(8, 6); System.out.println(res); } private static int gcd(int i, int j) { int m, n, r; // 使m>n if (i > j) { m = i; n = j; } else { m = j; n = i; } // 通过辗转除来求的最大公约数 r = m % n; while (r != 0) { m = n; n = r; r = m % n; } // 返回最大公约数 return n; } }
自然语言描述
计算两个非负整数p 和q 的最大公约数:若
q 是0,则最大公约数为p。否则,将p 除以
q 得到余数r,p 和q 的最大公约数即为q 和
r 的最大公约数。
Java code 求公约数
public static int gcd(int p, int q)
{
if (q == 0) return p;
int r = p % q;
return gcd(q, r);
}
公倍数就是两个数的积除以最大公约数。
public static int g(int p, int q)
{
return p*q/gcd(q, r);
}
java输入两个正整数m和n,求其最大公约数和最小公倍数
public static void main(String[] args) { \/\/ TODO Auto-generated method stub \/\/调用java.util.Scanner可以获得从键盘输入的数字;Scanner sc= new Scanner(System.in);\/\/定义两个整型数字的变量 int min;int max;System.out.print("请输入一个数:");min= sc.nextInt();\/\/nextInt();方法...
用java编写程序,输入两个正整数,利用辗转相除法求两个整数的最大公约...
计算两个非负整数p 和q 的最大公约数:若 q 是0,则最大公约数为p。否则,将p 除以 q 得到余数r,p 和q 的最大公约数即为q 和 r 的最大公约数。Java code 求公约数 public static int gcd(int p, int q){ if (q == 0) return p; int r = p % q; return gcd(q...
java:输入两个正整数m和n,求其最大公约数和最小公倍数。 程序分析:利 ...
程序运行截图:辗除法——辗转相除法, 又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。代码:public class Test {public static final void main(String[] args) {System.out.println("请输入两个正整数");System.out.print("第一个正整数:");Scanner scanner = new ...
输入2 个正整数m和n(1<=m,n<=10000),输出m 和n之间所有的Fibonacci数...
public static int fib(int n) { if (n==1||n==2) { return 1;}else { return fib(n-1)+fib(n-2);} } }
java程序设计:输入2 个正整数m和n(1<=m,n<=10000),输出m 和n之间所有...
修改一下main就行了 public static void main(String args[]) { int ri,repeat; int i, m, n; long f; Scanner in=new Scanner(System.in); repeat=in.nextInt(); for(ri=1; ri<=repeat; ri++) { m=in.nextInt(); n=in.nextInt(); for(i=1;...
java输入两个正整数m和n(m>=1,n<=1000),输出m到n之间的所有水仙花数...
int main(void){ int m,n,i,sum,a;printf("input m:");scanf("%d",&m);printf("input n:");scanf("%d",&n);\/\/int sum ;for(i=m;i<=n;i++){ a=i;sum=0;\/\/下一个数,sum要重新回零咯 ,找的我晕啊~\/*假设是153-153(没错)do{ sum=sum+pow(a-10*(a\/10),3);...
输入两个正整数m和n,求其最大公约数和最小公倍数.用JAVA编写
max % min); } } public static void getLCMAndGCD(int x, int y) { int gcd = getGCD(x,y); System.out.println("最大公约数:"+gcd); System.out.println("最小公倍数:"+x*y\/gcd); } public static void main(String[] args) { getLCMAndGCD(18, 8); }} ...
程序需要输入两个正整数(假设为n和m),程序输出行数为n、列数为m的如下...
} else{ \/\/输出空格 \/\/Console.Write(" "); \/\/C \/\/printf(" "); \/\/C \/\/System.out.printf(" "); \/\/Java } } \/\/输出换行 \/\/Console.Write("\\n"); \/\/C \/\/printf("\\n"); \/\/C \/\/System.out.printf("\\n"); \/\/Java } 根据你用的编程语言,取消上面的输出注释。
java输入两个正整数 m 和 k,判断 m 能否被19整除,且恰好含有k个3_百度...
1.m被19整除2.组成m的所有数字中,恰好有k个3代码如下boolean ret = false;if(m % 19 == 0){\/\/被19整除 \/\/计算数字3的个数 int temp = m; int last = 0; int count = 0; do{ last = temp%10;\/\/获取个位数字 if(last == 3){\/\/找到一个数字3 count++; ...
用JAVA程序写出:接收用户从键盘上输入的两个整数,求两个数的最大公约...
;Scanner sc=new Scanner(System.in);System.out.println("请输入第一个正整数");int NumA=sc.nextInt();System.out.println("请输入第二个正整数");int NumB=sc.nextInt();System.out.println("最大公约数是:"+g.gcd(NumA, NumB)+"\\n最小公倍数是:"+g.icm(NumA,NumB));} } ...