Каким будет самый простой способ вычисления Greatest Common Divisor и Less Common Common на множестве чисел? Какие математические функции можно использовать для поиска этой информации?
Как найти GCD, LCM для набора чисел
Ответ 1
Я использовал алгоритм Евклида, чтобы найти наибольший общий делитель двух чисел; это может быть повторено, чтобы получить 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 gcd(long[] input)
{
long result = input[0];
for(int i = 1; i < input.length; i++) result = lcm(result, input[i]);
return result;
}
Ответ 2
Существует алгоритм Евклида для 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)
Ответ 3
Для него нет встроенной функции. Вы можете найти 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 )
Ответ 4
Если вы можете использовать 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)));
}
Я ориентировался на Jeffrey Hantin answer, но
- вычислял gcd функционально
- использовал синтаксис varargs для более простого API (я не был уверен, будет ли перегрузка работать корректно, но это работает на моей машине)
- преобразовал gcd
numbers-Array в функциональный синтаксис, который более компактен и IMO легче читать (по крайней мере, если вы привыкли к функциональному программированию)
Этот подход, вероятно, немного медленнее из-за дополнительных вызовов функций, но это, вероятно, вообще не имеет значения для большинства случаев использования.
Ответ 5
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);
}
Ответ 6
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);
}
Ответ 7
В 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, оба метода не будут работать.
Ответ 8
Проще понять:
{ int num1,num2;
int m1,m2,r;
cout<<"Enter two numbers: "<<endl;
cin>>num1>>num2;
if(num1>num2)
{
m1=num1;
m2=num2;
}
else
{
m1=num2;
m2=num1;
}
while(r!=0)
{ r=m1%m2; m1=m2; m2=r;
}
cout<<"result of gcd of two number is "<<m1<<endl;
int lcm= (num1*num2)/m1;
cout<<"result of lcm of two number is "<<lcm;
}
- См. больше на: http://www.easycppcodes.com/2015/01/find-gcd-and-lcm-of-two-numbers-using.html#sthash.lAWwqgS5.dpuf
Ответ 9
для 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());
Ответ 10
В основном, чтобы найти 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));
}
}
Вы можете ссылаться на этот ресурс, чтобы найти примеры по алгоритму евклидова.
Ответ 11
int lcm(int x,int y){
int i=1;
while(true){
if(!(x*i)%y)
return x*i;
i++;
}
Ответ 12
import java.util.Scanner; public class 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
Ответ 13
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);
}
}
}
Ответ 14
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);
}
}
Ответ 15
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;
}
здесь, сначала для цикла, для получения каждого числа, начиная с "2". то если оператор if проверяет, будет ли число (i) делить lcm, если это произойдет, то оно пропустит это. и если это не так, то следующий для цикла - для поиска нет. который может делить число (i), если это произойдет, нам это не нужно. нам нужен только его дополнительный фактор. поэтому здесь, если флаг является истинным, это означает, что уже есть некоторые факторы нет. 'i' в lcm. поэтому мы делим эти факторы и умножаем дополнительный коэффициент на lcm. Если число не делится ни на один из его предыдущих нет. затем, когда просто умножьте его на lcm.
Ответ 16
int main()
{
int n1,n2,num1,num2,rem,gcd,lcm;
printf("Enter a number:");
scanf("%d %d",&num1,&num2);
num1=n1;
num2=n2;
while(num2!=0)
{
rem=num1%num2;
num1=num2;
num2=rem;
}
gcd=num1;
lcm=(n1*n2)/gcd;
printf("Gcd=%d\n",gcd);
printf("Lcm=%d\n",lcm);
}