标签: lcm

我刚刚开始使用Haskell并敲定了这个简单的递归算法,以便为列表中的每个数字找到LCM.它有效,但它很混乱,我希望有一些同行评论如何使这更优雅,可读和Haskell-y.

lcms list 
  | length list > 1 = lcms (lcm (head list) (head (tail list)):(tail (tail list)))
  | otherwise = list

因此,它采用一个列表并对前两个项目进行LCM,然后将其预先列出减去这两个元素.基本上,我想要的psudocode是这样的:

lcms [a,b,c] = lcm (a, (lcm (b, c))

任何建议,任何人？我渴望在Haskell上进行改进并撰写人们可以阅读的内容.效率提示也是受欢迎的!

谢谢,全部!

以下是我的代码,我尝试使用BigInteger inn Java计算从1到100的所有数字的LCM.但它没有提供任何答案.

import java.math.BigInteger;

public class CommonOneToHundred {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BigInteger res =new BigInteger("1");
        int i = 2;
        while(i<=100){
        res = lcm(res,BigInteger.valueOf(i));
        i++;
        }
        System.out.println(res);
    }
       static BigInteger lcm(BigInteger x, BigInteger y)
        {
            BigInteger a;
            //a = (x > y) ? x : y; // a is greater number
            a = y;
            while(true)
            {
                if(a.divide(x).equals(0) &&  a.divide(y).equals(0))
                    return a;
                a = a.add(BigInteger.ONE);
            }   
        }

}

我想创建一个表格来更好地说明我的问题

这是我在 oracle 数据库中的数据示例

我想做的工作是按以下步骤一步一步来的

1-按 group_id 列将分母列中的值分组并计算最小公倍数。对于此操作，我创建了 lcm（最小公倍数）和 gcd（最大公约数）函数。添加到这里。

CREATE OR REPLACE function SAMPLE.lcm(a number, b number) return number is begin return (a*b)/gcd(a,b); 结尾;

CREATE OR REPLACE function SAMPLE.gcd(a number, b number)
return number is
begin if b = 0 then return a; 否则返回 gcd(b,mod(a,b)); 万一; 结尾;

2-按分母列的值按比例增加分子值。像这样的数学公式：

(lcm(values of denominator(1..to -n)) / values of denominator ) * 分子的值

3-通过 group_id 值对新计算值进行分组来求和

使这项工作完成的所有项目，如 sql、function、view 都适合我。

我能为此做什么。

我有一个int数组,我正在尝试找到数组中所有值的LCM(最小公倍数).我已经分别写了一个lcm方法; 它需要两个值作为输入,并返回lcm.我的lcm方法工作得非常好,但当我用它来找到所有值的LCM时,我得到了错误的答案.

这里是我gcd和lcm方法:

public static int gcd(int a, int b){
    if (a<b) return gcd(b,a);
    if (a%b==0) return b;
    else return gcd(a, a%b);
}


public static int lcm(int a, int b){
    return ((a*b)/gcd(a,b));

} 

这就是我对lcm数组值的看法:

public static int lcmofarray(int[] arr, int start, int end){
    if ((end-start)==1) return lcm(arr[start],arr[end-1]);
    else return (lcm (arr[start], lcmofarray(arr, start+1, end)));
}

当我输入一个数字为1到5 的数组arr,0 start和数组的长度为时end,我得到30作为答案,而我想要60.当我输入一个包含从1到1的所有数字的数组时10,我得到840而不是2520.我实在无法解释.

该算法应该工作 - 我已经在脑海中解决了这个问题.无法弄清楚我的代码有什么问题.

任何帮助将不胜感激.

我一直在努力学习编程,所以我一直在努力创建一个简单的程序,它将两个数字作为输入,并计算最低的公共倍数.我在Python中这样做是因为我不知道如何在Java中输入.现在发生的事情是,在我输入数字后程序就会挂起,没有任何反应.这里的任何指针将不胜感激.谢谢.

#LCM Calculator
#Author: Ethan Houston
#Language: Python
#Date: 2013-12-27
#Function: Program takes 2 numbers as input, and finds the lowest number
# that goes into each of them

def lcmCalculator(one, two):
    """ takes two numbers as input, computes a number that evenly 
        divides both numbers """
    counter = 2 #this is the number that the program tried to divide each number by.
                #it increases by 1 if it doesn't divide evenly with both numbers.
    while True:
        if one % …

我想使用欧几里得算法计算值数组的最小公倍数

我正在使用这个伪代码实现:在维基百科上找到

function gcd(a, b)
    while b ? 0
       t := b; 
       b := a mod b; 
       a := t; 
    return a;

我的javascript实现就是这样

function smallestCommons(arr) {

  var gcm = arr.reduce(function(a,b){

    let minNum = Math.min(a,b);
    let maxNum = Math.max(a,b);
    var placeHolder = 0;

    while(minNum!==0){
        placeHolder = maxNum;
        maxNum = minNum;
        minNum = placeHolder%minNum;
    } 

    return (a*b)/(minNum);
  },1);

  return gcm;
}


smallestCommons([1,2,3,4,5]);

在我的whileloop上我得到错误

无限循环

编辑进行了一些修正,在gcm函数结束时,我使用0作为初始起始值,它应该是1,因为你不能从0开始有一个gcm.

EDIT2预期输出应为60,因为这是1,2,3,4,5的最小公倍数

问题 ：

我的解决方案：

该解决方案有效，但不幸的是，当k很大时它真的太慢了（例如，k 可以是与 69533550916004 一样大的数字）

var k = 14;
var res = 0;
for(let i = 1; i <= k; i++){
  for(let j = 1; j <= k; j++){
    res += lcm(i, j);
  }
}
console.log(res)

function lcm(a,b){
  return (a * b) / gcd(a,b);
}

function gcd(a,b){
  if(!b){
    return a; 
  }  
  return gcd(b, a % b); 
}

谢谢

问题5: 2520是可以除以1到10中的每个数字而没有任何余数的最小数字.可以被1到20的所有数字整除的最小正数是多少？

我已经解决了Project Euler的问题5

这是Java代码:

 static long FindLcm(long a,long b)
 {
     long lcm,hcf = 0;
     long i=1;
     long ger=a>b?a:b;
     while(i<ger)
     {
         if((a%i==0) && (b%i==0))
             hcf=i;
         i++;
     }
     lcm=(a*b)/hcf;
     return lcm;
 }
 static void FindMultiple()
 {
     long lcm=1;
     for(long i=2;i<=20;i++)
     {
         lcm=FindLcm(lcm,i);
     }   
     System.out.println("Lcm="+lcm);
 }

怎么能优化这个？

我在LCM上解决了以下问题:计算N个模数为1000000007的LCM

我的方法:

typedef unsigned long long ull;
const ull mod=1000000007;
ull A[10009];
/*Euclidean GCD*/
ull gcd(ull a,ull b)
{
    while( b != 0)
    {
        ull  t = b;
        b= a %t;
        a = t;
    }
    return a;
}
ull lcm(ull a, ull b) 
{ 
    return (a/gcd(a,b))%mod*(b%mod); 
}
ull lcms(int  l ,ull * A)
{
    int     i;
    ull result;
    result = 1;
    for (i = 0; i < l; i++) 
        result = lcm(result, A[i])%1000000007;
    return result;
}
int main()
{ …

在 R 中，我有两个辅助函数

gcf(x,y) 求两个数的最大公因数

和

lcm(x,y) 用于查找两个数字的租用公倍数。

例如，

> gcd(85,75)
[1] 5
> lcm(20,50)
[1] 100

现在，我需要创建一个函数，该函数将整数向量作为返回元素的最小公倍数的参数。

例如，

lcm_vector(c(20,50,75)) = 300

我知道这需要计算

LCM(20, 50, 75) = LCM(LCM(20, 50), 75)。

但是我如何处理向量的元素？我需要循环吗？

我的LCM计划结果出错了.

如果找到数字的gcd,然后用gcd划分产品.

int gcd(int x, int y)
{
  while(y != 0)
  {
    int save = y;
    y = x % y;
    x = save;
  }
  return y;
}

int lcm(int x, int y)
{
  int prod = x * y;
  int Gcd = gcd(x,y);
  int lcm = prod / Gcd;

  return lcm;
}

任何帮助非常感谢.

我正在使用JavaScript,我正在解决最小的公共倍数,两个数字,并且最小的公共倍数必须可以被两个数字之间的所有数字整除.

现在,我的代码根本不工作,没有返回任何内容.我有一个函数来计算最小公倍数和第二个函数来确定该倍数是否可被最小和最大数字之间的数字整除.

function smallestCommons(arr) {

    var max = 0;
    var min = 0;
    var lcm = 0;
    var max2 = 0;
       if(arr[0]> arr[1]) {
         max = arr[0];
         min = arr[1];
       } else {
         max = arr[1];
         min = arr[0];
       }

       function range(item){
         for(var j = min+1; j < max; j++){
           if(item % j !== 0){
             return 0;
           } else {
             return item;
           }
         }
       }   
       function lcmFind(min1, max1){
         for(var i =1; i < min1; i++){
             max1 = max1 * i; …

我使用的公式是“两个数的乘积等于它们的 GCD 和 LCM 的乘积”。

这是我的代码：

# Uses python3

import sys

def hcf(x, y):

    while(y):
        x, y = y, x % y

    return x

a,b = map(int,sys.stdin.readline().split())

res=int(((a*b)/hcf(a,b)))
print(res)

它适用于小数字。但是当我输入时：

输入：226553150 1023473145

我的输出：46374212988031352

正确输出：46374212988031350

谁能告诉我我哪里错了？