How do you write a program which calculating LCM of 2 numbers in Linux?

Answer 1

Dunno about Linux, but I've written mine in C.

It prime factorises the numbers, making a note of the highest power of each prime factor as it goes (in a linked list of malloc()ed structures). Once all the numbers have been factorised, it has a list of all the primes used along with their highest power. The lcm is then the product of the primes raised to their highest power.

You are also not limited to the lcm of 2 numbers - you can keep factorising numbers until you run out of them and find the lcm of them all!

Whilst you're at it you can add finding their hcf very easily: this time it's the product of the common primes to their lowest power.

All that is then needed is the prime factorisation of the numbers.

The normal method is:

1. try the first prime (2)
2. If it does not divide the number:
   1. set the prime to the next prime
   2. Try again from step 2
3. Add one to the power count of this prime
4. replace the number by the number divided by the prime
5. if the number is not 1 go back to step 2
6. Found all primes, stop!

Finding the primes by which to divide is not easy on the fly, so you could check 2 specifically and then all odd numbers 3, 5, 7,..., but an improvement is to specifically check 2 and 3 and then check the numbers 6n ± 1 (which may be prime and why are 6n, 6n ± 2 and 6n ± 3 definitely not prime?) which skips every third odd number - this sequence of potential primes (5, 7, 11, 13, 17, 19, ...) can be easily generated.

And while you're at it, you could display the prime factorisation you've done.

And using that prime factorisation you can list the factors (and factor pairs) for the numbers.

Obviously you'll need to sort out how the numbers are input to the program - I decode argv[], but you could use reading from stdin if you prefer.