I need to find least common divisor for a series of numbers (up to 100 000 numbers, each of them is in the range of [0, 2 000 000 000])
I am using the following algorithm lcm(a,b) = (a/gcd(a,b)) * b
The standard method of finding lcm for for than 2 numbers lcm(a, lcm(b,c))... is working for small input values.
However, for large input, it starts giving overflow error even if i used long long int...
How can I avoid having overflow error for many larger integer values?
Thank you for the help
Least common multiple in this case can be a large number with hundreds of digits. You need to handle such big integers.
gmplib library (-lgmp) supports arbitrary precision integer arithmetic:
int have_read_first_number = 0;
mpz_t result, arg;
mpz_inits(result, arg, NULL);
mpz_set_ui(arg, 1u);
/* read decimal integers from stdin: one per line */
while((len = getline(&token, &capacity, stdin)) > 0) {
if (!have_read_first_number) { /* read the first integer */
parse_mpz(token, result);
have_read_first_number = 1; /* successfully read first integer */
}
else { /* read the rest of the numbers */
parse_mpz(token, arg);
}
/* lcm(a, b, c, d) = lcm(lcm(lcm(a, b), c), d) */
mpz_lcm(result, result, arg);
}
if (!have_read_first_number) /* error */
panic("no numbers read");
/* print result as decimal */
mpz_out_str(stdout, 10, result);
puts("");
Example:
$ gcc lcm.c -o lcm -lgmp && { seq 1 100 | ./lcm; }
69720375229712477164533808935312303556800