Do you think sorting would help here?
I mean, arranging the numbers in descending order and then computing
progressively.
Why I am suggesting sorting is that considering an array like the
following
2, 80, 36, 70, 150, 300
It would be pretty expensive to do the euclidean algo first with
gcd(2, 80 ) = 2 --- O(40)
gcd(2, 36 )= 2 -- O(18)
gcd(2 , 70) =
gcd(2, 150)
vs
gcd(150, 300) = 150
gcd(70,150) = 10
etc..
gcd (a,b)
{
if ( b > a )
b = b % a
else
a= a % b
} //this is same as euclidean algorithm.
On Aug 12, 9:25 pm, Muntasir Azam Khan <[EMAIL PROTECTED]>
wrote:
> On Aug 12, 9:54 pm, "sumedh sakdeo" <[EMAIL PROTECTED]> wrote:
>
>
>
> > well i have made this ...
>
> > · Find minimum of n numbers.
>
> > · Run loop from i=1 to minimum number
>
> > · Check if i is divisible by all the three numbers
>
> > · If yes, gcd=i
>
> > · Continue the step till you get the gcd which is less than or equal
> > to minimum of three numbers
> > anyone can do it less complexity?
>
> > On 8/12/07, Muntasir Azam Khan <[EMAIL PROTECTED]> wrote:
>
> > > Google is your friend.
>
> > > ----- Original Message -----
> > > *From:* sumedh sakdeo <[EMAIL PROTECTED]>
> > > *To:* algogeeks@googlegroups.com
> > > *Sent:* Sunday, August 12, 2007 9:37 PM
> > > *Subject:* [algogeeks] Algo to get GCD of given numbers
>
> > > Write algorithm for finding the GCD of given numbers.
>
> Try thishttp://en.wikipedia.org/wiki/Euclidean_algorithm
>
> Once you can find the gcd of two numbers, you can easily extend this
> to get the GCD of n numbers.
>
> gcd(a,b,c )= gcd ( a, gcd( b, c ) )
>
> Hope this helps,
> Muntasir
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
