【Java】白俊1934号


白駿1934号。


最小公倍数


質問する


2つの自然数AとBについて、Aの倍数でありBの倍数である自然数をAとBの公倍数と呼ぶ.この公倍数の中で最小の数を最小公倍数と呼ぶ.例えば、6及び15の公倍数は30、60、90等であり、最小公倍数は30である.
2つの自然数AとBが与えられた場合、AとBの最小公倍数を求めるプログラムを作成してください.

入力


第1行は、試験例の個数T(1≦T≦1000)を与える.2行目からT行にまたがり、AとBが与えられる.(1 ≤ A, B ≤ 45,000)

しゅつりょく


1行目から、T行入力AとBの最小公倍数の順に1行ずつ出力します.



コード#コード#

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();	
		StringTokenizer st;
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			int z = gcd(x, y);
			
			sb.append(x * y / z).append('\n');
		}
		System.out.println(sb);
	}

	public static int gcd(int a, int b) {
		while (b != 0) {
			int r = a % b; 
			// GCD(a, b) = GCD(b, r)
			a = b;
			b = r;
		}
		return a;
	}
}

に答える


コードのgcdは最大公約数である.最小公倍数は、2つの数の積を最大公倍数で割った値です.(a*b)/gcd(a,b)