โปรแกรมหา ห.ร.ม. กับการเขียนฟังก์ชัน gcd

บทความนี้เราจะมาเขียนโปรแกรม เพื่อหาค่า ห.ร.ม. กันครับ
ห.ร.ม. คือ อะไร และหาได้ยังไง ดูได้ตามลิ้ง การหา ห.ร.ม. กับ อัลกอริทึมของยุคลิด

โปรแกรมหา ห.ร.ม. แบบแยกตัวประกอบ

 public static void main(String[] args) { 	Scanner in = new Scanner(System.in); 	System.out.print("Input First for GCD : "); 	int first = in.nextInt(); 	System.out.print("Input Second for GCD : "); 	int second = in.nextInt(); 	System.out.println(gcd(first, second)); } public static int gcd(int first, int second){ 	List compoundFirst = new ArrayList(); // แยกตัวประกอบตัวแรก 	int num = 2; 	while(num < first){ 		if(first%num == 0){ 			compoundFirst.add(num); 			first = first/num; 			num = 1; 		} 		num++; 	} 	compoundFirst.add(first); 	List compoundSecond = new ArrayList(); // แยกตัวประกอบตัวที่สอง 	num = 2; 	while(num < second){ 		if(second%num == 0){ 			compoundSecond.add(num); 			second = second/num; 			num = 1; 		} 		num++; 	} 	compoundSecond.add(second); 	int result = 1; 	for (int i = 0; i < compoundFirst.size(); i++) { 		for (int j = 0; j < compoundSecond.size(); j++) { 			if(compoundFirst.get(i) == compoundSecond.get(j)){ // เช็คว่าเหมือนกันหรือเปล่า 				result *= compoundSecond.get(j); 				compoundSecond.remove(j); 				break; 			} 		} 	} 	return result; } 

โปรแกรมหา ห.ร.ม. แบบหารสั้น

 public static void main(String[] args) { 	Scanner in = new Scanner(System.in); 	System.out.print("Input First for GCD : "); 	int first = in.nextInt(); 	System.out.print("Input Second for GCD : "); 	int second = in.nextInt(); 	System.out.println(gcd(first, second)); } public static int gcd(int first, int second){ 	if(first%second == 0 || second%first == 0) { 		return Math.min(first, second); 	} 	int result = 1; 	int num = 2; 	int min = Math.min(first, second); 	while(num < min){ 		if(first%num == 0 && second%num == 0){ // เช็คว่าหารทั้งสองตัวลงตัว 			result = num*result; 			first = first/num; 			second = second/num; 			num = 1; 		} 		num++; 	} 	return result; } 

โปรแกรมหา ห.ร.ม. แบบอัลกอริทึมของยุคลิด

หา ห.ร.ม. โดยวิธีอัลกอริทึมของยุคลิด แบบใช้ while

 public static void main(String[] args) { 	Scanner in = new Scanner(System.in); 	System.out.print("Input First for GCD : "); 	int first = in.nextInt(); 	System.out.print("Input Second for GCD : "); 	int second = in.nextInt(); 	System.out.println(gcd(first, second)); } public static int gcd(int first, int second){ 	if(first%second == 0) { 		return Math.min(first, second); 	} 	int result = 1; 	while(first%second != 0){ 			result = first%second; 			first = second; 			second = result; 	} 	return result; } 

หา ห.ร.ม. โดยวิธีอัลกอริทึมของยุคลิด แบบการเขียนฟังก์ชัน แบบ recursive

 public static void main(String[] args) { 	Scanner in = new Scanner(System.in); 	System.out.print("Input First for GCD : "); 	int first = in.nextInt(); 	System.out.print("Input Second for GCD : "); 	int second = in.nextInt(); 	System.out.println(gcd(first, second)); } public static int gcd(int a, int b){ 	if(a%b == 0) { 		return b; 	} 	//System.out.println(a + " = " + b + "*" + a/b + " + " + a%b); 	return gcd(b, a%b); }