Wypisaywanie najwiekszego dzielnika dwóch liczb.

Question

Witam, napisałem program, który znajduje największy dzielnik dwóch liczb, jednak teraz mam problem, ponieważ program wypisuje wszystkie dzielniki, a nie wiem za bardzo jak wypisać tylko największy dzielnik. Próbowałem wsadzić wyniki do tablicy, jednak się nie udało.

import java.util.Scanner;

public class Zadanie7 {

    public static void main(String[] args) {

        int n=0,m=0, wynik=0, licznik;
        Scanner scan = new Scanner(System.in);
        int[] tablica = new int[100];

        do {
            System.out.print("7. Podaj nie ujemna liczbe n: ");
            n = scan.nextInt();
        }while (n<0);

        do {
            System.out.print("7. Podaj nie ujemna liczbe m: ");
            m = scan.nextInt();
        }while (m<0);

        licznik=n*m;
        for(int i=1; i<=licznik; i++){
            if(n%i==0 && m%i==0){
                System.out.println("Najwiekszy wspolny dzielnik jest : "+i);
            }
        }
        System.out.println("Wynik "+wynik);
    }
}

Czy ktoś ma pomysł, jak rozwiązać ten problem?

Answer 1

Możesz użyć algorytmu Euklidesa.

Możesz to zrobić rekurencyjnie, np.

public static int gcd(int a, int b){
    if (b==0) return a;
    else return gcd(b,a%b);
}

Albo z użyciem pętli while:

while (b!=0){
    int temp=b;
    b=a%b;
    a=temp;
}

 

Comments

Dziekuję ;)