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))); }я ориентировалась на Джеффри Hantin это, а
- рассчитал gcd функционально
- использовал Varargs-синтаксис для более простого API (я не был уверен, что перегрузка будет работать правильно, но на моей машине)
- преобразовал gcd из
numbers- массив в функциональный синтаксис, который является более компактный и Имо легче читать (по крайней мере, если вы привыкли к функциональному программированию)этот подход, вероятно, немного медленнее из-за дополнительных вызовов функций, но это, вероятно, не имеет никакого значения для большинства случаев применения.
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(); }GCD:
private static int gcd(int numberOne, int numberTwo) { return (numberTwo == 0) ? numberOne : gcd(numberTwo, numberOne % numberTwo); }конечно, если один из аргументов равен 0, оба метода не будут работать.
на
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());
в основном, чтобы найти 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)); } }Вы можете обратиться этой ресурс для поиска примеров по алгоритму Евклида.
импорт java.утиль.Сканер; публичный класс 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); } } }
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); } }
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, если это так, то он пропускает это нет. и если это не так, то следующий цикл для поиска нет. который может делить число (i), Если это произойдет, нам это не нужно. нам нужен только его дополнительный фактор. поэтому здесь, если флаг истинен, это означает, что уже были некоторые факторы no. "я" в НОК. поэтому мы делим эти факторы и умножаем дополнительный фактор на lcm. Если число не делится ни на одно из его предыдущих нет. тогда просто умножьте его на НОК.
Comments