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?
Hint ...
Try finding prime factors of each number,
then, gather up (multiply) all the common primes.
thanks!
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?
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).
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.