java公因數

A. 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));
}
}

B. 編寫java Application輸入兩個數並找出兩個數的最大公因數

import java.util.Scanner;

public class Du2 {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.print("請輸入第一個數字 ");
int num1 = scanner.nextInt();

System.out.print("請輸入第2個數字 ");
int num2 = scanner.nextInt();

int temp = num1;

num1 = num1 < num2? num1: num2;
num2 = temp > num2? temp: num2;

for(int num = num1; num >= 1; num--){
if(num1 % num == 0 && num2 % num == 0){
System.out.println("最大公約數為 : " + num);
break;
}
}

}

}

C. 如何用JAVA求兩個整數的最大公因數

public class Test {
public static void main(String[] args){
Test t = new Test();
int x = 240;
int y = 880;
System.out.println(t.gcd(x,y));
}
private int gcd(int x,int y){
int re = 0;
while(x!=y){
if(x>y){
x=x-y;
re =x;
gcd(x,y);
}
else{
y=y-x;
re = y;
gcd(x,y);
}
}
return re;
}
}
運行結果：
80

D. Java編程題：計算數字12和18的最小公倍數。求答案。

下面給出了一個計算兩個整數的最大公約數和最小公倍數的通用的方法：
首先先計算最大的公約數，最小公倍數=兩個數的乘積再除以它們的最大公約數。

public class Test2 {
public static void main(String[] args) {
System.out.println(lcm(12, 18));
}

/**
* 計算整數a和b的最大公約數
*/
public static int gcd(int a, int b) {
while(b!=0) {
int tmp = b;
b = a%b;
a = tmp;
}
return a;
}
/**
* 計算整數a和b的最小公倍數
*/
public static int lcm(int a, int b) {
int t = gcd(a,b);
if(t==0) return 0;
else
return a * b / t;
}
}

E. java 最大公因數，最小公倍數，因式分解如何寫這些方法

package neusoft.com.test;

public class Test2 {
public static void main(String args[]){
int x = 18,y = 39;
int result1 = getMax(x,y);
System.out.println(result1);
int result2 = getMin(x,y);
System.out.println(result2);
}
//最大公約數
public static int getMax(int x,int y){
int tmp = 0;
if(x > y){
tmp = y;
}else{
tmp = x;
}
for(int i = tmp; i >= 1; i--){
if(x % i == 0 && y % i == 0){
return i;
}
}

return -1;
}
//最小公倍數
public static int getMin(int x,int y){
int tmp = 0;
if(x < y){
tmp = y;
}else{
tmp = x;
}
for(int i = tmp; i > 0; i++){
if(i % x == 0 && i % y == 0){
return i;
}
}

return -1;
}
}