最小公倍数 java
今天起床迟了，30多个小时的连续作战，睡个懒觉也无可厚非。。。
然后看到一个题目，一个很另类的记录整个求两个整数的最小公倍数的过程。于是小写了一下，发现过程中问题还不少，果然底层代码一段时间不写就生疏了。
先看两个简洁方法求最小公倍数
一最常用
两数之积 分别同时除以 两数，能同时除得整数的为公倍数，最小者为最小公倍数，当然，从最小数开始循环，第一个公倍数即为最小：
假定两个数分别为m,n
if(m二：效率很高的写法
两数相乘除去两数中重复部分即可
int minMultiple(int a, int b) {
int r = a, s = a, t = b;
if (a < b) {
r = a;
a = b;
b = r;
}
while (r != 0) {
r = a % b;
a = b;
b = r;
}
return s * t / a;
} 三：模拟中学时代的最小公倍数求法
还记得吗，我们写两个数到一排，然后在左边分别写出两个数都有的部分，然后重复，最后把框框外的数相乘即为最小公倍数。
package calcumulation;
import java.util.ArrayList;
import java.util.Scanner;
public class LCM {
static int a;
static int b;
static ArrayList primeNumber;
public static void main(String []args){
Scanner in= new Scanner(System.in);
//note:I do not know what the size of your a and b ,
//so I am just give you the prime number that less than 100,you can change it below
LCM.findPrime();
System.out.println(primeNumber);
tag: while(in.hasNext()){a = in.nextInt();
b = in.nextInt();
//test 0,if zero,simple,do nothing and continue...
if(a==0 ||b ==0) continue tag;
int [][] aTable = new int[primeNumber.size()][2];
int [][] bTable = new int[primeNumber.size()][2];
;
/***********table cal************/
for(int i = 0;
i < primeNumber.size() ;
i++){
for(int j = 0;
j < primeNumber.size() ;
j++){
if( a%primeNumber.get(i) == 0 ) {
aTable[i][0] = primeNumber.get(i);
aTable[i][1]++;
a = a/primeNumber.get(i);
}
if( b%primeNumber.get(i) == 0 ) {
bTable[i][0] = primeNumber.get(i);
bTable[i][1]++;
b = b/primeNumber.get(i);
}
}
}
//end cal table/************print LCM******************/
int i=0,j=0;
while(aTable[i][0] != 0){
System.out.println("This is show a prime number is :"+aTable[i][0] +" occurs "+aTable[i][1]);
i++;
}
while(bTable[j][0] != 0){
System.out.println("This is show b prime number is :"+bTable[j][0] +" occurs "+bTable[j][1]);
j++;
}int result = 1;
//get the same value of a and b
int [] temp = new int[primeNumber.size()];
int k = 0;
for(int m = 0;
m < primeNumber.size() ;
m++){
if(aTable[m][0] !=0 ){
for(int n = 0;
n < primeNumber.size() ;
n++){
if(aTable[m][0] == bTable[n][0]) {
temp[k] = aTable[m][0];
k++;
aTable[m][1]--;
bTable[n][1]--;
}//inner if
}//inner for
}//if outer
}
int l = 0;
while(temp[l] !=0) { result *=temp[l];
l++;
}// previous value multiple the rest of not identical value
for(int m = 0;
m < primeNumber.size() ;
m++){
if(aTable[m][0] !=0 && aTable[m][1] >0) result *=(aTable[m][0] * aTable[m][1] );
}
for(int n = 0;
n < primeNumber.size() ;
n++){
if(bTable[b][0] !=0 && bTable[n][1] >0) result *= (bTable[n][0] * bTable[n][1] );
}//print
System.out.println(" LCM is :" + result);
}//end outer for
}//end non-daemon//prime cal
staticvoid findPrime(){
//get prime number less than 100
primeNumber = new ArrayList();
label: for (int i = 2;
i < 100;
i++) {
int sqrt = (int) Math.sqrt(i);
if(i ==2 || i%2 != 0){
for( int j=2;
j <=sqrt ;
j++){
if( i%j == 0) continue label;
}
primeNumber.add(i);
}
}
}
}
输出测试：
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
120
150
This is show a prime number is :2 occurs 3
This is show a prime number is :3 occurs 1
This is show a prime number is :5 occurs 1
This is show b prime number is :2 occurs 1
This is show b prime number is :3 occurs 1
This is show b prime number is :5 occurs 2
30
LCM is :600
150
180
This is show a prime number is :2 occurs 1
This is show a prime number is :3 occurs 1
This is show a prime number is :5 occurs 2
This is show b prime number is :2 occurs 2
This is show b prime number is :3 occurs 2
This is show b prime number is :5 occurs 1
30
LCM is :900【最小公倍数 java】
推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 2019-02-13——今天谈梦想（）
- Ⅴ爱阅读，亲子互动——打卡第178天
- 我错了，余生不再打扰
- 今天写一些什么
- 2019.4.18感恩日记
- 事件代理
- “不完美，才美”01（190410）
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树