LCM algorithm with 3 numbers without the use of GCD | Sololearn: Learn to code for FREE!
New course! Every coder should learn Generative AI!
Try a free lesson
+ 1

LCM algorithm with 3 numbers without the use of GCD I am having some slight issues with my current code where in some cases like: S = 11 M = 21 L = 30 This will make the first term 3 times as big as the actual LCM of the three values which makes it skip a lot of multiples. The first output for Test1 should be 2310 but it outputs 6930 instead. There are of course other cases like: A = 101 B = 202 C = 303 This should get the LCM of 606 but does 303*202 = 61206 instead. I am unsure as to how I should go about fixing it as I want it to be as it is right now as it is many times faster when it comes to higher values and I am going for efficiency and semi ease to read. So if you can find a fix using math that’d be great as everything so far has used only that. It’d also be fun to see someone try to make a more efficient algorithm for it with only 10 lines of code which is standard formatting, no one-liners and everything within functions counts as code and everything outside does not count towards the lines of code. Challenge: 1) Pass 4 values into a function which gets the shared multiples of all 3 values up to a limit. 2) Output all multiples Example: A=3, B = 5, C = 7 and limit = 100 this would output nothing as the first common multiple of all 3 is 105

29th Oct 2020, 3:13 PM
YayL - avatar
1 Answer
Unfortunately, i don't think you can have lcm without gcd (if you could, then gcd would be a*b/lcm - so that would mean that you just have a faster gcd algorithm) Instead, why don't you look at fast gcd algorithms, and optimize one for your problem? A simple Euclid algorithm would require around 50 divisions at worst for int arguments (twice that much for int64), a binary gcd would need about 32(64) iterations, each a subtraction and some bit shifts. I don't think that would slow you program in a big way. If you need to work with multiple precision integers, maybe its worth looking how gmp does it.
6th Nov 2020, 6:56 PM
Volodymyr Chelnokov
Volodymyr Chelnokov - avatar