Results 1 to 5 of 5
  1. #1
    Join Date
    Mar 2009
    Posts
    2
    Rep Power
    0

    Default 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..

    Please help!!

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    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. #3
    rdtindsm is offline Member
    Join Date
    Feb 2009
    Posts
    92
    Rep Power
    0

    Default 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 .


    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

  4. #4
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    abuse reported

  5. #5
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

Similar Threads

  1. Help about Guess the Numbers Program in java
    By macfrik in forum New To Java
    Replies: 6
    Last Post: 03-25-2009, 03:59 AM
  2. prime numbers program
    By i contra i in forum New To Java
    Replies: 9
    Last Post: 01-15-2009, 07:22 AM
  3. Why my program cannot calculate the decimal value?
    By pearllymary78 in forum New To Java
    Replies: 4
    Last Post: 06-23-2008, 12:52 AM
  4. Replies: 0
    Last Post: 03-28-2008, 08:46 PM
  5. Calculate Tax in java
    By toby in forum New To Java
    Replies: 2
    Last Post: 07-30-2007, 09:03 AM

Posting Permissions

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