『壹』 java做二個數的最大公約數
1、歐幾里德演算法和擴展歐幾里德演算法
歐幾里德演算法
歐幾里德演算法又稱輾轉相除法，用於計算兩個整數a,b的最大公約數。其計算原理依賴於下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
證明：a可以表示成a = kb + r，則r = a mod b
假設d是a,b的一個公約數，則有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公約數
假設d 是(b,a mod b)的公約數，則
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公約數
因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證
歐幾里德演算法就是根據這個原理來做的，其演算法用C++語言描述為：
void swap(int & a, int & b)
{
int c = a;
a = b;
b = c;
}
int gcd(int a,int b)
{
if(0 == a )
{
return b;
}
if( 0 == b)
{
return a;
}
if(a > b)
{
swap(a,b);
}
int c;
for(c = a % b ; c > 0 ; c = a % b)
{
a = b;
b = c;
}
return b;
}
2、Stein演算法
歐幾里德演算法是計算兩個數最大公約數的傳統演算法，他無論從理論還是從效率上都是很好的。但是他有一個致命的缺陷，這個缺陷只有在大素數時才會顯現出來。
考慮現在的硬體平台，一般整數最多也就是64位，對於這樣的整數，計算兩個數之間的模是很簡單的。對於字長為32位的平台，計算兩個不超過32位的整數的模，只需要一個指令周期，而計算64位以下的整數模，也不過幾個周期而已。但是對於更大的素數，這樣的計算過程就不得不由用戶來設計，為了計算兩個超過64位的整數的模，用戶也許不得不採用類似於多位數除法手算過程中的試商法，這個過程不但復雜，而且消耗了很多CPU時間。對於現代密碼演算法，要求計算128位以上的素數的情況比比皆是，設計這樣的程序迫切希望能夠拋棄除法和取模。
Stein演算法由J. Stein 1961年提出，這個方法也是計算兩個數的最大公約數。和歐幾里德演算法 演算法不同的是，Stein演算法只有整數的移位和加減法，這對於程序設計者是一個福音。
為了說明Stein演算法的正確性，首先必須注意到以下結論：
gcd(a,a) = a，也就是一個數和他自身的公約數是其自身
gcd(ka,kb) = k gcd(a,b)，也就是最大公約數運算和倍乘運算可以交換，特殊的，當k=2時，說明兩個偶數的最大公約數必然能被2整除
C++/java 實現
// c++/java stein 演算法
int gcd(int a,int b){
if(a<b)//arrange so that a>b{
int temp = a;
a = b;
b=temp;
}
if(0==b)//the base case
return a;
if(a%2==0 && b%2 ==0)//a and b are even
return 2*gcd(a/2,b/2);
if ( a%2 == 0)// only a is even
return gcd(a/2,b);
if ( b%2==0 )// only b is even
return gcd(a,b/2);
return gcd((a+b)/2,(a-b)/2);// a and b are odd
}
『貳』 用java從鍵盤輸入兩個正整數，求他們的最大公約數
從鍵盤輸入那麼就會用到Java的Scanner類，最大公約數，這里會用到演算法，網路上面也有，下面是其中一種：
importjava.util.Scanner;
publicclassTestDivisor{
publicstaticvoidmain(String[]args){
Scannerinput=newScanner(System.in);//新建一個輸入流對象，這里會導包
System.out.println("請輸入第一個數：");
intnum1=input.nextInt();//接收輸入的整數
System.out.println("請輸入第二個數：");
intnum2=input.nextInt();//接收輸入的整數
intnum3=num1%num2;//num1跟num2取余得到num3
while(num3>0){
num1=num2;
num2=num3;
num3=num1%num2;
}
input.close();//關閉輸入流
System.out.println("最大公約數是："+num2);
}
}
/**
GCD演算法的實現--GCB是最大公約數縮寫
2.1遞歸實現
intgcd(inta,intb)
{
if(!b)returna;
elsereturngcd(b,a%b);
}
2.2迭代實現
intgcd(inta,intb)
{
intc=a%b;
while(c){
a=b;
b=c;
c=a%b;
}
returnb;
}
*
*/
『叄』 java中如何求兩個數的最大公約數
求最大公約數：提示用戶輸入兩個正整數，並求出它們的最大公約數。
方法一：（輾轉相除法）
設用戶輸入的兩個整數為n1和n2且n1>n2，余數=n1%n2。當余數不為0時，把除數賦給n1做被除數，把余數賦給n2做除數再求得新余數，若還不為0再重復知道余數為0，此時n2就為最大公約數。
例：gcd(20,8)
20=2*8+4
8=2*4 因此gcd(20,8)=4
代碼實現：
import javax.swing.JOptionPane;public class GreatestCommonDivisor{ public static void main(String[] args){
String num1String = JOptionPane.showInputDialog("Please enter the first integer:"); int num1 = Integer.parseInt(num1String);
String num2String = JOptionPane.showInputDialog("Please enter the second integer:"); int num2 = Integer.parseInt(num2String); if(num1<num2){ int temp=num1;
num1=num2;
num2=temp;
} int remainder = num1%num2; int n1=num1,n2=num2; while(remainder!=0){
num1=num2;
num2=remainder;
remainder=num1%num2;
}
JOptionPane.showMessageDialog(null,String.format("The greatest common divisor for %d and %d is %d.",n1,n2,num2));
}
}
方法二：假設輸入的兩個整數為n1和n2，檢查k(k=2,3,4…)是否為n1和n2的最大公約數，直到k大於兩個數中較小的一個。
代碼實現：
import javax.swing.JOptionPane;public class GreatestCommonDivisor{ public static void main(String[] args){
String num1String = JOptionPane.showInputDialog("Please enter the first integer:"); int num1 = Integer.parseInt(num1String);
String num2String = JOptionPane.showInputDialog("Please enter the second integer:"); int num2 = Integer.parseInt(num2String); int gcd=1,k=1; while(k<=num1 && k<=num2)
{ if(num1%k==0 && num2%k==0)
gcd=k;
k++;
}
JOptionPane.showMessageDialog(null,String.format("The greatest common divisor for %d and %d is %d.",num1,num2,gcd));
}
}
『肆』 java求兩個數的最大公約數和最小公倍數
先求出兩個數的最大公約數，計算的方法有很多，最簡單的一種就是採用輾轉相除法，求得兩個數的最大公約數以後，在計算原來的兩數的乘積除以最大公約數，就是這兩個數的最小公倍數。
『伍』 java最大公約數演算法
三種演算法：
//歐幾里得演算法（輾轉相除）：
public static int gcd(int m,int n) {
if(m<n) {
int k=m;
m=n;
n=k;
}
//if(m%n!=0) {
// m=m%n;
// return gcd(m,n);
//}
//return n;
return m%n == 0?n:gcd(n,m%n);
}
//連續整數檢測演算法：
public static int gcd1(int m,int n) {
int t;
if(m<n) {
t=m;
}else {
t=n;
}
while(m%t!=0||n%t!=0){
t--;
}
return t;
}
//公因數法：(更相減損）
public static int gcd2(int m,int n) {
int i=0,t,x;
while(m%2==0&n%2==0) {
m/=2;
n/=2;
i++;
}
if(m<n){
t=m;
m=n;
n=t;
}
while(n!=(m-n)) {
x=m-n;
m=(n>x)?n:x;
n=(n<x)?n:x;
}
if(i==0)
return n;
else
return (int)Math.pow(2, i)*n;
}
public static void main(String[] args) {
System.out.println("請輸入兩個正整數:");
Scanner scan = new Scanner(System.in);
Scanner scan2=new Scanner(System.in);
int m=scan.nextInt();
int n=scan2.nextInt();
System.out.println("歐幾里得演算法求最大公約數是:"+gcd(m,n));
System.out.println("連續整數檢測演算法求最大公約數是:"+gcd1(m,n));
System.out.println("公因數法求最大公約數是:"+gcd2(m,n));
}
}
『陸』 用java求兩數的最大公約數和最小公倍數。
import java.util.*;
public class lianxi06 {
public static void main(String[] args) {
int a ,b,m;
Scanner s = new Scanner(System.in);
System.out.print( "鍵入一個整數： ");
a = s.nextInt();
System.out.print( "再鍵入一個整數： ");
b = s.nextInt();
deff cd = new deff();
m = cd.deff(a,b);
int n = a * b / m;
System.out.println("最大公約數: " + m);
System.out.println("最小公倍數: " + n);
}
}
class deff{
public int deff(int x, int y) {
int t;
if(x < y) {
t = x;
x = y;
y = t;
}
while(y != 0) {
if(x == y) return x;
else {
int k = x % y;
x = y;
y = k;
}
}
return x;
}
}
『柒』 JAVA輸入2個數，求他們的最大公約數。
package com.code;
import java.util.Scanner;
public class TestRun {
public static void main(String[] args) {
int m;
int n;
int temp;
Scanner input = new Scanner(System.in);
m = input.nextInt();
n = input.nextInt();
if (m > n) {
temp = n;
} else {
temp = m;
}
for (int i= temp; i >= 1; i--) {
if (m % i == 0 && n % i == 0) {
temp=i;
break;
}
}
System.out.println("temp:" +temp );
}
}
1、break指跳出當前循環，當i從temp開始減小到為公約數時，break跳出循環就好了，return指跳出整個方法，所以後面的語句都不執行了。
2、最後輸出的temp值你的程序是沒有變的，temp是個參照，i才是變化的數字，當i減小到合要求時，將I賦值給temp此時temp才為公約數，否則temp一直是輸入數值中較小的那個。
3、兩個數要除的數值應該為逐漸減小的 i，而不是一直不變的temp
『捌』 JAVA求2個整數的最大公約數
public
class
CommonDivisor
{
public
static
void
main(String[]
args)
{
int
n1
=
21;
int
n2
=
14;
System.out.println("最大公約數是"
+
fun(n1,
n2));
}
public
static
int
fun(int
n1,
int
n2)
{
int
m
=
1;
if
(n1
<
n2)
{
int
t
=
n1;
n1
=
n2;
n1
=
t;
}
for
(int
i
=
n2;
i
>
1;
i--)
{
if
((n1
%
i
==
0)
&&
(n2
%
i
==
0))
{
return
i;
}
}
return
m;
}
}
//
the
end