Как найти GCD, LCM по набору номеров
Какой самый простой способ вычислить Величайший общий делитель и наименьшее общее кратное для набора чисел? Какие математические функции можно использовать, чтобы найти эту информацию?
13 ответов
Я использовал алгоритм Евклида, чтобы найти наибольший общий делитель двух чисел; это может быть повторено, чтобы получить GCD большего набора чисел.
private static long gcd(long a, long b)
{
while (b > 0)
{
long temp = b;
b = a % b; // % is remainder
a = temp;
}
return a;
}
private static long gcd(long[] input)
{
long result = input[0];
for(int i = 1; i < input.length; i++) result = gcd(result, input[i]);
return result;
}
Наименьшее общее множитель немного сложнее, но, вероятно, лучший подход - сокращение с помощью GCD, которое можно повторить аналогичным образом:
private static long lcm(long a, long b)
{
return a * (b / gcd(a, b));
}
private static long lcm(long[] input)
{
long result = input[0];
for(int i = 1; i < input.length; i++) result = lcm(result, input[i]);
return result;
}
Есть алгоритм Евклида для GCD,
public int GCF(int a, int b) {
if (b == 0) return a;
else return (GCF (b, a % b));
}
Кстати, a а также b должно быть больше или равно 0и LCM = |ab| / GCF(a, b)
Для него нет встроенной функции. Вы можете найти GCD из двух чисел, используя алгоритм Евклида.
Для набора номера
GCD(a_1,a_2,a_3,...,a_n) = GCD( GCD(a_1, a_2), a_3, a_4,..., a_n )
Примените это рекурсивно.
То же самое для LCM:
LCM(a,b) = a * b / GCD(a,b)
LCM(a_1,a_2,a_3,...,a_n) = LCM( LCM(a_1, a_2), a_3, a_4,..., a_n )
Если вы можете использовать Java 8 (и действительно хотите), вы можете использовать лямбда-выражения для решения этой проблемы:
private static int gcd(int x, int y) {
return (y == 0) ? x : gcd(y, x % y);
}
public static int gcd(int... numbers) {
return Arrays.stream(numbers).reduce(0, (x, y) -> gcd(x, y));
}
public static int lcm(int... numbers) {
return Arrays.stream(numbers).reduce(1, (x, y) -> x * (y / gcd(x, y)));
}
Я сосредоточился на ответе Джеффри Хантина, но
- рассчитал жкд функционально
- использовал синтаксис varargs для более простого API (я не был уверен, будет ли корректно работать перегрузка, но на моей машине это работает)
- превратил жкд
numbers-Введите в функциональный синтаксис, который является более компактным и IMO легче для чтения (по крайней мере, если вы привыкли к функциональному программированию)
Этот подход, вероятно, немного медленнее из-за дополнительных вызовов функций, но это, вероятно, не будет иметь значения вообще для большинства случаев использования.
int gcf(int a, int b)
{
while (a != b) // while the two numbers are not equal...
{
// ...subtract the smaller one from the larger one
if (a > b) a -= b; // if a is larger than b, subtract b from a
else b -= a; // if b is larger than a, subtract a from b
}
return a; // or return b, a will be equal to b either way
}
int lcm(int a, int b)
{
// the lcm is simply (a * b) divided by the gcf of the two
return (a * b) / gcf(a, b);
}
int lcmcal(int i,int y)
{
int n,x,s=1,t=1;
for(n=1;;n++)
{
s=i*n;
for(x=1;t<s;x++)
{
t=y*x;
}
if(s==t)
break;
}
return(s);
}
В Java 8 есть более элегантные и функциональные способы решения этой проблемы.
LCM:
private static int lcm(int numberOne, int numberTwo) {
final int bigger = Math.max(numberOne, numberTwo);
final int smaller = Math.min(numberOne, numberTwo);
return IntStream.rangeClosed(1,smaller)
.filter(factor -> (factor * bigger) % smaller == 0)
.map(factor -> Math.abs(factor * bigger))
.findFirst()
.getAsInt();
}
НОД:
private static int gcd(int numberOne, int numberTwo) {
return (numberTwo == 0) ? numberOne : gcd(numberTwo, numberOne % numberTwo);
}
Конечно, если один аргумент равен 0, оба метода не будут работать.
В основном, чтобы найти gcd и lcm на наборе чисел, вы можете использовать формулу ниже,
LCM(a, b) X HCF(a, b) = a * b
Между тем в Java вы можете использовать алгоритм Евклида, чтобы найти gcd и lcm, как это
public static int GCF(int a, int b)
{
if (b == 0)
{
return a;
}
else
{
return (GCF(b, a % b));
}
}
Вы можете обратиться к этому ресурсу, чтобы найти примеры алгоритма Евклида.
За gcd вы можете сделать, как показано ниже:
String[] ss = new Scanner(System.in).nextLine().split("\\s+");
BigInteger bi,bi2 = null;
bi2 = new BigInteger(ss[1]);
for(int i = 0 ; i<ss.length-1 ; i+=2 )
{
bi = new BigInteger(ss[i]);
bi2 = bi.gcd(bi2);
}
System.out.println(bi2.toString());
public class HcfLcm {
public static void main(String[] args) {
System.out.println("HCF: "+ getHcf(20, 15)); //5
System.out.println("LCM: "+ getLcm2(20, 15)); //60
}
private static Integer getLcm2(int n1, int n2) {
int lcm = Math.max(n1, n2);
// Always true
while (true) {
if (lcm % n1 == 0 && lcm % n2 == 0) {
break;
}
++lcm;
}
return lcm;
}
private static Integer getLcm(int i, int j) {
int hcf = getHcf(i, j);
return hcf * i/hcf * j/hcf; // i*j*hcf
}
private static Integer getHcf(int i, int j) {
while(i%j != 0) {
int temp = i%j;
i = j;
j = temp;
}
return j;
}
}
Импорт java.util.Scanner; открытый класс Lcmhcf {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner scan = new Scanner(System.in);
int n1,n2,x,y,lcm,hcf;
System.out.println("Enter any 2 numbers....");
n1=scan.nextInt();
n2=scan.nextInt();
x=n1;
y=n2;
do{
if(n1>n2){
n1=n1-n2;
}
else{
n2=n2-n1;
}
} while(n1!=n2);
hcf=n1;
lcm=x*y/hcf;
System.out.println("HCF IS = "+hcf);
System.out.println("LCM IS = "+lcm);
}
}
//## Heading ##By Rajeev Lochan Sen
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n0 = input.nextInt(); // number of intended input.
int [] MyList = new int [n0];
for (int i = 0; i < n0; i++)
MyList[i] = input.nextInt();
//input values stored in an array
int i = 0;
int count = 0;
int gcd = 1; // Initial gcd is 1
int k = 2; // Possible gcd
while (k <= MyList[i] && k <= MyList[i]) {
if (MyList[i] % k == 0 && MyList[i] % k == 0)
gcd = k; // Update gcd
k++;
count++; //checking array for gcd
}
// int i = 0;
MyList [i] = gcd;
for (int e: MyList) {
System.out.println(e);
}
}
}
int lcm = 1;
int y = 0;
boolean flag = false;
for(int i=2;i<=n;i++){
if(lcm%i!=0){
for(int j=i-1;j>1;j--){
if(i%j==0){
flag =true;
y = j;
break;
}
}
if(flag){
lcm = lcm*i/y;
}
else{
lcm = lcm*i;
}
}
flag = false;
}
здесь первый цикл for предназначен для получения всех чисел, начинающихся с '2'. тогда, если оператор проверяет, делит ли число (i) lcm, если это так, то он пропускает это нет. и если это не так, то следующий цикл for для поиска нет. который может делить число (I), если это произойдет, нам не нужно, что нет. нам нужен только дополнительный фактор. так что здесь, если флаг имеет значение true, это означает, что там уже были некоторые факторы нет. "Я" в lcm. поэтому мы делим эти факторы и умножаем дополнительный коэффициент на lcm. Если число не делится ни на один из его предыдущих нет. затем, когда просто умножить его на lcm.
import java.util.*;
public class lcm {
public static void main(String args[])
{
int lcmresult=1;
System.out.println("Enter the number1: ");
Scanner s=new Scanner(System.in);
int a=s.nextInt();
System.out.println("Enter the number2: ");
int b=s.nextInt();
int max=a>b?a:b;
for(int i=2;i<=max;i++)
{
while(a%i==0||b%i==0)
{
lcmresult=lcmresult*i;
if(a%i==0)
a=a/i;
if(b%i==0)
b=b/i;
if(a==1&&b==1)
break;
}
}
System.out.println("lcm: "+lcmresult);
}
}