0

Hello guys. I need an idea. How can I calculate GCF of many numbers? I thought I could calculate two by two numbers, but it not seems to be a very effective idea. There is my function:

int gcf (unsigned int x, unsigned int y)
{
    return (y == 0) ? x : gcf (y, x % y);
}

Help? Please?

Edited by BogdanCov

4
Contributors
4
Replies
26
Views
2 Years
Discussion Span
Last Post by tapananand
Featured Replies
  • 2

    Hint ... Try finding prime factors of each number, then, gather up (multiply) all the common primes. Read More

  • You do not need to use seive algo here at all. Prime factors of a number can be found in sqrt(n) without the seive. You can store the count of each prime factor in an array. Initialize the HCF with the first number. Then if count of any of the … Read More

2

Hint ...
Try finding prime factors of each number,
then, gather up (multiply) all the common primes.

0

EDIT: Original suggestion was silly... revised:
Use the same technique, but don't use recursion like that. It should be able to outperform most prime number based algorithms (plus it's simpler).

Also, how are you 'folding' the method over all of the numbers?

Edited by Hiroshe

1

You do not need to use seive algo here at all. Prime factors of a number can be found in sqrt(n) without the seive. You can store the count of each prime factor in an array. Initialize the HCF with the first number. Then if count of any of the prime factors(say p) for the next(and subsequent numbers) becomes less than what is in the array, update the array and divide the hcf by: p^(difference between what is in the array and the current count).

The total complexity of this algo will be: (sum of sqrt of all numbers) * (some log term - due to power - calculated in logn).

Edited by tapananand

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.