# Thread: Program in Java To calculate GCD of n numbers.?

1. Member
Join Date
Mar 2009
Posts
2
Rep Power
0

## Program 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..

2. 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?

3. Member
Join Date
Feb 2009
Posts
92
Rep Power
0

## gcd 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 .

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

4. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
abuse reported

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•