Stack Overflow
Stack Overflow

Questions tagged [lcm]

LCM(a, b) is the smallest positive integer that is divisible by both a and b.

Least common multiple (also called the lowest common multiple or smallest common multiple) of two integers a and b, usually denoted by LCM(a, b), is the smallest positive integer that is divisible by both a and b.

166 questions
175
votes
32 answers

Least common multiple for 3 or more numbers

How do you calculate the least common multiple of multiple numbers? So far I've only been able to calculate it between two numbers. But have no idea how to expand it to calculate 3 or more numbers. So far this is how I did it LCM = num1 * num2 / …
paan
  • 7,054
  • 8
  • 38
  • 44
85
votes
17 answers

What is the most efficient way to calculate the least common multiple of two integers?

What is the most efficient way to calculate the least common multiple of two integers? I just came up with this, but it definitely leaves something to be desired. int n=7, m=4, n1=n, m1=m; while( m1 != n1 ){ if( m1 > n1 ) n1 += n; …
farm ostrich
  • 5,881
  • 14
  • 55
  • 81
72
votes
13 answers

How to find GCD, LCM on a set of numbers

What would be the easiest way to calculate Greatest Common Divisor and Least Common Multiple on a set of numbers? What math functions can be used to find this information?
user339108
  • 12,613
  • 33
  • 81
  • 112
28
votes
16 answers

C++ algorithm to calculate least common multiple for multiple numbers

Is there a C++ algorithm to calculate the least common multiple for multiple numbers, like lcm(3,6,12) or lcm(5,7,9,12)?
Askener
  • 291
  • 1
  • 3
  • 4
24
votes
8 answers

Least Common Multiple

I have the current coding which used to be a goto but I was told to not use goto anymore as it is frowned upon. I am having troubles changing it into for say a while loop. I am fairly new to C# and programming in general so some of this is…
Tristan M.
  • 347
  • 1
  • 2
  • 9
22
votes
14 answers

Finding the LCM of a range of numbers

I read an interesting DailyWTF post today, "Out of All The Possible Answers..." and it interested me enough to dig up the original forum post where it was submitted. This got me thinking how I would solve this interesting problem - the original…
Jay
  • 41,768
  • 14
  • 66
  • 83
9
votes
2 answers

GCD and LCM relation

The following relation works only for two (3, 12) numbers, it fails to produce the right answer when used for three numbers (3,12,10) . Just wondering if is it my understanding or it is just for two numbers and for me same is true for Euclid…
Abidi
  • 7,846
  • 14
  • 43
  • 65
9
votes
7 answers

Faster algorithm to find how many numbers are not divisible by a given set of numbers

I am trying to solve an online judge problem: http://opc.iarcs.org.in/index.php/problems/LEAFEAT The problem in short: If we are given an integer L and a set of N integers s1,s2,s3..sN, we have to find how many numbers there are from 0 to L-1 which…
2147483647
  • 1,177
  • 3
  • 13
  • 33
9
votes
3 answers

What's the most efficient algorithm to calculate the LCM of a range of numbers?

I looked around and found other questions that had answers but none of them address the scope of this particular question., including this question, and also this one. I have to compute the LCM of large ranges of numbers in an efficient way. I…
Wug
  • 12,956
  • 4
  • 34
  • 54
5
votes
2 answers

Least Common Multiple of an array values using Euclidean Algorithm

I want to calculate the least common multiple of an array of values, using Euclideans algorithm I am using this pseudocode implementation: found on wikipedia function gcd(a, b) while b ≠ 0 t := b; b := a mod b; a := t; …
Vincent Tang
  • 3,758
  • 6
  • 45
  • 63
5
votes
4 answers

How to calculate Least common multiple of {1, 2, 3, .........., n}?

How to find LCM of {1, 2, ..., n} where 0 < n < 10001 in fastest possible way. The one way is to calculate n! / gcd (1,2,.....,n) but this can be slow as number of testcases are t < 501 and the output should be LCM ( n! ) % 1000000007 Code for the…
DCoder
  • 127
  • 11
4
votes
4 answers

How to calculate all the prime factors of lcm of n integers?

I have n integers stored in an array a, say a[0],a[1],.....,a[n-1] where each a[i] <= 10^12 and n <100. Now, I need to find all the prime factors of the LCM of these n integers i.e., LCM of {a[0],a[1],.....,a[n-1]} I have a method but I need a more…
dark_shadow
  • 3,503
  • 11
  • 56
  • 81
4
votes
2 answers

How can I optimize my C / x86 code?

int lcm_old(int a, int b) { int n; for(n=1;;n++) if(n%a == 0 && n%b == 0) return n; } int lcm(int a,int b) { int n = 0; __asm { lstart: inc n; mov eax, n; mov edx, 0; idiv a; …
user181351
3
votes
1 answer

Bazel Link .so libraries located in a completely different, very remote folder

Folks, I am trying to link .h and static libraries into my tensorflow program. My headers are in /usr/local/include/lcm And static/shared libraries (.so, etc.) in /usr/local/lib But Bazel complains they don't exist, or that it cannot find them.…
Pototo
  • 691
  • 1
  • 12
  • 27
3
votes
2 answers

Given a set of numbers,find the pair which has the least LCM(Lowest Common Multiple)

I used this approach. Found all possible nC2 pairs possible for n numbers. Then individually found thier LCM by computing their GCD and dividing the product of the two numbers by thier GCD. Also maintained a variable which contained the least LCM…
Krishna Bagaria
  • 37
  • 1
  • 3
1
2 3
…
11 12