I have already made it for two numbers.But help me for any n numbers.

Please make it as simple as possible because i have just started learning java and i am stuck here..

Please help!!

Printable View

- 03-28-2009, 04:51 PMankitsinghal_89Program in Java To calculate GCD of n numbers.?
I have already made it for two numbers.But help me for any n numbers.

Please make it as simple as possible because i have just started learning java and i am stuck here..

Please help!! - 03-28-2009, 06:15 PMEranga
So whats the logic you have followed to do this? Did you use a specific algorithm for calculation or your own way? How did you do it for 2 number?

- 03-28-2009, 08:54 PMrdtindsmgcd n
When I started contemplating the problem, I got the feeling a brute force method would be computationally demanding. Although my initial research suggested the problem was np-complete, I also found that Algorithm 386 by Bradley is linear in time and space. Many of the sources for the paper are academic and require a professional subscription or access as a student. I finally found this source and downloaded it.

h t t p : / / w w w .

eknigu.com/.../Bradley.%20Algorithm%20386

Warning: do not go directly to the home page. It's Russian.

The paper is in djvu format. Do a search to find the reader, it's open source.

You will have to port your code from a FORTRAN program, but it's not a terribly long program, less then 80 lines including comments and GOTOs.

Rots of Ruck.

from another forum

**********

the greatest common denominator of n+1 numbers, where n is a number of values for which you have already generated a GCD, is the GCD of the next value you want to put in your calculation and the GCD you have already obtained. For example, take a function int GCD(36, 24) that would return 12. Then let's say we overload it to take three numbers, int GCD(36, 24, 18) which would return 6. If you already have the code for the first function that got the GCD of two numbers, you have half the code already, because GCD(36, 24, 18) will return the same value as GCD(GCD(36, 24), 18), or GCD(12, 18). All you need to do, then, is modify your code to work on an array or list of values and pass that data by reference recursively to calculate the GCD of the next two values, with a base case being that you are processing the last two values in the set.

This is, however, based off of my knowledge of C++, I'm not sure how those techniques would work in Java.

In pseudocode, where <T> is a data type that contains the n values you're calculating:

void nGCD(<T> values)

{

...Begin at the first two values of <T>.

...Calculate the GCD of those two variables, store it in the

...second variable. The code you already wrote goes here.

...Delete the first variable.

...Move forward by one variable. The second variable

...becomes the new first variable.

...If (the new second variable exists in <T>)

......nGCD(values)

}

The GCD of all of the numbers in <T> will be stored in the last variable of <T>.

**********

Also found this in C

********

#include<stdio.h>

#include<conio.h>

void main(){

int a[10],b[10],q,i,j,min,max,cnt;

cnt=max=q=0;

clrscr();

printf("Enter the no of values to find GCD");

canf("%d",&i);

for(j=0;j<i;j++){

printf("enter the element %d\n",(j+1));

scanf("%d",&a[j]);

} //for

min=a[0];

for(j=0;j<i;j++) {

if(min>a[j]) {

min=a[j]; }

} for

for(j=1;j<=min;j++) { //for 1

for(int k=0;k<i;k++) {

if(a[k]%j==0){

++cnt;} // if

}

if(cnt==i) {

b[q]=j;

++q;} //if

cnt=0;

} //outer for

for(int p=0;p<q;p++) {

if(max<b[p]) {

max=b[p]; } // if

} // for

printf("The GCD is %d",max);

getch();

}

**************

The first algorithm is from a peer reviewed paper.

Haven't really studied the other two, but they seem to be saying to reursively call gcd on each pair (gcd(n, gcd (n-1, Gcd(n-2 ...(Gcd N1, N0)))...). Don't know if complexity is linear or higher.

If you want to ignore the fact that I have'nt read the code carefully, this should work

lst = {dat0, dat1 ...., datn}

iGcd = dat0

lst = rest of list

while lst {

iGcd = GCD(iGcd, head of list)

lst = rest of list

} //while

Rots of Ruck - 02-15-2011, 10:08 AMpbrockway2
abuse reported

- 02-15-2011, 10:23 AMEranga