複数の数の最小公倍数をどのように計算しますか?
これまでのところ、2 つの数値の間でしか計算できませんでした。しかし、それを拡張して 3 つ以上の数を計算する方法がわかりません。
これまでのところ、これは私がやった方法です
LCM = num1 * num2 / gcd ( num1 , num2 )
gcd は、数値の最大公約数を計算する関数です。ユークリッド アルゴリズムの使用
しかし、3つ以上の数の計算方法がわかりません。
157554 次
32 に答える
194
2 つの数値の最小公倍数を繰り返し計算することにより、3 つ以上の数値の最小公倍数を計算できます。
lcm(a,b,c) = lcm(a,lcm(b,c))
于 2008-09-29T04:37:31.660 に答える
150
Python の場合 ( primes.py を変更):
def gcd(a, b):
"""Return greatest common divisor using Euclid's Algorithm."""
while b:
a, b = b, a % b
return a
def lcm(a, b):
"""Return lowest common multiple."""
return a * b // gcd(a, b)
def lcmm(*args):
"""Return lcm of args."""
return reduce(lcm, args)
使用法：
>>> lcmm(100, 23, 98)
112700
>>> lcmm(*range(1, 20))
232792560
reduce()そのような作品：
>>> f = lambda a,b: "f(%s,%s)" % (a,b)
>>> print reduce(f, "abcd")
f(f(f(a,b),c),d)
于 2008-09-29T04:44:40.147 に答える
27
ECMA スタイルの実装は次のとおりです。
function gcd(a, b){
// Euclidean algorithm
while (b != 0){
var temp = b;
b = a % b;
a = temp;
}
return a;
}
function lcm(a, b){
return (a * b / gcd(a, b));
}
function lcmm(args){
// Recursively iterate through pairs of arguments
// i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))
if(args.length == 2){
return lcm(args[0], args[1]);
} else {
var arg0 = args[0];
args.shift();
return lcm(arg0, lcmm(args));
}
}
于 2010-04-14T21:48:38.557 に答える
6
私はHaskellでこれを理解しました：
lcm' :: Integral a => a -> a -> a
lcm' a b = a`div`(gcd a b) * b
lcm :: Integral a => [a] -> a
lcm (n:ns) = foldr lcm' n ns
私は自分のgcd関数を書くのに時間をかけましたが、プレリュードでそれを見つけるだけでした！今日はたくさんのことを学びました：D
于 2010-01-26T21:54:06.607 に答える
6
gcdの関数を必要としないいくつかのPythonコード：
from sys import argv
def lcm(x,y):
tmp=x
while (tmp%y)!=0:
tmp+=x
return tmp
def lcmm(*args):
return reduce(lcm,args)
args=map(int,argv[1:])
print lcmm(*args)
ターミナルでは次のようになります。
$ python lcm.py 10 15 17
510
于 2012-08-07T17:54:27.803 に答える
3
以下は、Virgil Disgr4ce の実装の C# ポートです。
public class MathUtils
{
/// <summary>
/// Calculates the least common multiple of 2+ numbers.
/// </summary>
/// <remarks>
/// Uses recursion based on lcm(a,b,c) = lcm(a,lcm(b,c)).
/// Ported from http://stackoverflow.com/a/2641293/420175.
/// </remarks>
public static Int64 LCM(IList<Int64> numbers)
{
if (numbers.Count < 2)
throw new ArgumentException("you must pass two or more numbers");
return LCM(numbers, 0);
}
public static Int64 LCM(params Int64[] numbers)
{
return LCM((IList<Int64>)numbers);
}
private static Int64 LCM(IList<Int64> numbers, int i)
{
// Recursively iterate through pairs of arguments
// i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))
if (i + 2 == numbers.Count)
{
return LCM(numbers[i], numbers[i+1]);
}
else
{
return LCM(numbers[i], LCM(numbers, i+1));
}
}
public static Int64 LCM(Int64 a, Int64 b)
{
return (a * b / GCD(a, b));
}
/// <summary>
/// Finds the greatest common denominator for 2 numbers.
/// </summary>
/// <remarks>
/// Also from http://stackoverflow.com/a/2641293/420175.
/// </remarks>
public static Int64 GCD(Int64 a, Int64 b)
{
// Euclidean algorithm
Int64 t;
while (b != 0)
{
t = b;
b = a % b;
a = t;
}
return a;
}
}'
于 2012-12-05T20:26:29.997 に答える
3
数値のリストの lcm を検索する関数:
def function(l):
s = 1
for i in l:
s = lcm(i, s)
return s
于 2016-11-20T12:52:42.830 に答える
3
そしてScalaバージョン：
def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
def gcd(nums: Iterable[Int]): Int = nums.reduce(gcd)
def lcm(a: Int, b: Int): Int = if (a == 0 || b == 0) 0 else a * b / gcd(a, b)
def lcm(nums: Iterable[Int]): Int = nums.reduce(lcm)
于 2016-11-14T19:09:59.413 に答える
2
LINQ を使用すると、次のように記述できます。
static int LCM(int[] numbers)
{
return numbers.Aggregate(LCM);
}
static int LCM(int a, int b)
{
return a * b / GCD(a, b);
}
追加する必要がusing System.Linq;あり、例外を処理することを忘れないでください...
于 2014-04-24T12:27:31.957 に答える
1
別の方法で行うことができます-n個の数があるとします。連続する数のペアを取り、そのlcmを別の配列に保存します。最初の反復プログラムでこれを行うと、n / 2回の反復が実行されます。次に、（0,1）、（2,3）などのように0から始まるペアを取得します。LCMを計算して別の配列に格納します。1つの配列が残るまでこれを行います。（nが奇数の場合、lcmを見つけることはできません）
于 2011-09-14T06:56:56.057 に答える
1
配列要素の gcd と lcm を探していたところ、次のリンクで適切な解決策が見つかりました。
https://www.hackerrank.com/challenges/between-two-sets/forum
次のコードが含まれます。gcd のアルゴリズムは、以下のリンクで詳しく説明されているユークリッド アルゴリズムを使用します。
private static int gcd(int a, int b) {
while (b > 0) {
int temp = b;
b = a % b; // % is remainder
a = temp;
}
return a;
}
private static int gcd(int[] input) {
int result = input[0];
for (int i = 1; i < input.length; i++) {
result = gcd(result, input[i]);
}
return result;
}
private static int lcm(int a, int b) {
return a * (b / gcd(a, b));
}
private static int lcm(int[] input) {
int result = input[0];
for (int i = 1; i < input.length; i++) {
result = lcm(result, input[i]);
}
return result;
}
于 2016-12-26T13:21:22.203 に答える
1
R では、関数mGCD (x) およびmLCM (x) をパッケージnumbersから使用して、整数ベクトル x 内のすべての数値の最大公約数と最小公倍数を一緒に計算できます。
library(numbers)
mGCD(c(4, 8, 12, 16, 20))
[1] 4
mLCM(c(8,9,21))
[1] 504
# Sequences
mLCM(1:20)
[1] 232792560
于 2015-04-05T15:15:35.113 に答える
1
楽しみのために、シェル（ほぼすべてのシェル）の実装：
#!/bin/sh
gcd() { # Calculate $1 % $2 until $2 becomes zero.
until [ "$2" -eq 0 ]; do set -- "$2" "$(($1%$2))"; done
echo "$1"
}
lcm() { echo "$(( $1 / $(gcd "$1" "$2") * $2 ))"; }
while [ $# -gt 1 ]; do
t="$(lcm "$1" "$2")"
shift 2
set -- "$t" "$@"
done
echo "$1"
試してみてください：
$ ./script 2 3 4 5 6
取得するため
60
最大の入力と結果は、それよりも小さい必要があります。そうしない(2^63)-1と、シェルの計算がラップされます。
于 2016-11-25T00:56:21.307 に答える
0
clc;
data = [1 2 3 4 5]
LCM=1;
for i=1:1:length(data)
LCM = lcm(LCM,data(i))
end
于 2014-04-25T03:09:29.890 に答える
0
これはどう？
from operator import mul as MULTIPLY
def factors(n):
f = {} # a dict is necessary to create 'factor : exponent' pairs
divisor = 2
while n > 1:
while (divisor <= n):
if n % divisor == 0:
n /= divisor
f[divisor] = f.get(divisor, 0) + 1
else:
divisor += 1
return f
def mcm(numbers):
#numbers is a list of numbers so not restricted to two items
high_factors = {}
for n in numbers:
fn = factors(n)
for (key, value) in fn.iteritems():
if high_factors.get(key, 0) < value: # if fact not in dict or < val
high_factors[key] = value
return reduce (MULTIPLY, ((k ** v) for k, v in high_factors.items()))
于 2013-05-30T02:53:00.890 に答える
0
メソッド compLCM はベクトルを取り、LCM を返します。すべての数値はベクトル in_numbers 内にあります。
int mathOps::compLCM(std::vector<int> &in_numbers)
{
int tmpNumbers = in_numbers.size();
int tmpMax = *max_element(in_numbers.begin(), in_numbers.end());
bool tmpNotDividable = false;
while (true)
{
for (int i = 0; i < tmpNumbers && tmpNotDividable == false; i++)
{
if (tmpMax % in_numbers[i] != 0 )
tmpNotDividable = true;
}
if (tmpNotDividable == false)
return tmpMax;
else
tmpMax++;
}
}
于 2015-04-30T21:05:04.370 に答える
0
GCD は、負の数を少し修正する必要があります。
def gcd(x,y):
while y:
if y<0:
x,y=-x,-y
x,y=y,x % y
return x
def gcdl(*list):
return reduce(gcd, *list)
def lcm(x,y):
return x*y / gcd(x,y)
def lcml(*list):
return reduce(lcm, *list)
于 2013-01-04T18:03:08.470 に答える
0
Ruby では、次のように簡単です。
> [2, 3, 4, 6].reduce(:lcm)
=> 12
> [16, 32, 96].reduce(:gcd)
=> 16
(Ruby 2.2.10 および 2.6.3 でテスト済み)
于 2020-05-21T10:13:28.920 に答える
0
LCM は、結合的かつ可換的です。
LCM(a,b,c)=LCM(LCM(a,b),c)=LCM(a,LCM(b,c))
C のサンプル コードは次のとおりです。
int main()
{
int a[20],i,n,result=1; // assumption: count can't exceed 20
printf("Enter number of numbers to calculate LCM(less than 20):");
scanf("%d",&n);
printf("Enter %d numbers to calculate their LCM :",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
result=lcm(result,a[i]);
printf("LCM of given numbers = %d\n",result);
return 0;
}
int lcm(int a,int b)
{
int gcd=gcd_two_numbers(a,b);
return (a*b)/gcd;
}
int gcd_two_numbers(int a,int b)
{
int temp;
if(a>b)
{
temp=a;
a=b;
b=temp;
}
if(b%a==0)
return a;
else
return gcd_two_numbers(b%a,a);
}
于 2015-02-23T05:16:26.777 に答える
0
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a%b);
}
int lcm(int[] a, int n) {
int res = 1, i;
for (i = 0; i < n; i++) {
res = res*a[i]/gcd(res, a[i]);
}
return res;
}
于 2016-09-15T15:51:35.383 に答える
0
私たちはCalcullaに最小公倍数を実装しており、ステップを表示する任意の数の入力に対して機能します。
私たちがしていることは次のとおりです。
0: Assume we got inputs[] array, filled with integers. So, for example:
inputsArray = [6, 15, 25, ...]
lcm = 1
1: Find minimal prime factor for each input.
Minimal means for 6 it's 2, for 25 it's 5, for 34 it's 17
minFactorsArray = []
2: Find lowest from minFactors:
minFactor = MIN(minFactorsArray)
3: lcm *= minFactor
4: Iterate minFactorsArray and if the factor for given input equals minFactor, then divide the input by it:
for (inIdx in minFactorsArray)
if minFactorsArray[inIdx] == minFactor
inputsArray[inIdx] \= minFactor
5: repeat steps 1-4 until there is nothing to factorize anymore.
So, until inputsArray contains only 1-s.
それだけです - あなたはあなたのLCMを手に入れました。
于 2015-02-05T16:26:47.500 に答える