Największy wspólny dzielnik używając pętli

0

Hej
Musze napisać program który dla dwóch całkowitych i dodatnich liczb znajdzie największy wspólny dzielnik. Musze też do tego użyć pętli. Napisałam coś takiego ale dostaje błąd:

Error:(14, 24) java: incompatible types: boolean cannot be converted to int

Nie wiem w ogóle czy to dobrze robię proszę o pomoc.

public class NajwiekszyWspolnyDzielnik {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("Wprowadz pierwsza liczbe");
        int n = input.nextInt();
        System.out.println("Wprowadz druga liczbe");
        int m = input.nextInt();
        int nwd = 1;
        int nwdn = 1;
        for (int i=1; i<=m; i++){
            nwd = (int)((m%i) == 0);
            nwdn = (int) ((n%i) == 0);
            
        }
        if (nwd == nwdn) System.out.println(nwd);
        else System.out.println("Najwiekszy wspolny dzielnik nie istnieje");
    }
}
2

Bo to

(m % i) == 0 

może mieć tylko 2 wartości true albo false - ma to sens bo sprawdzasz czy reszta z dzielenia m przez i wynosi 0, są tylko 2 odpowiedzi - tak albo nie.

0

Jakaś podpowiedz jak to mogę zrobić? Nie używać modulo?

2

Źle indeksujesz pętlę – wartość początkowa dzielnika powinna wynosić tyle, ile mniejsza z dwóch liczb. Więc najpierw ustal początkową wartość dzielnika, a następnie w pętli sprawdzaj czy modulo dzielenia obu liczb jest równe 0. Jeśli jest to zwróć wartość dzielnika, a jeśli nie – dekrementuj dzielnik o 1 i wykonuj pętlę dalej. W najgorszym przypadku rezultatem będzie 1.

1

Dlaczego?

Bardziej musiałabyś zmienić to co jest w pętli for.
Sprawdzać czy n podzielone na i daje 0 i czy m podzielone na i daje 0. Jeżeli oba warunki są prawdziwe (&&) wtedy do nwd przypisujesz i.

Twój kod można uprościć, nie potrzebujesz nwdn bo wystarczy że zainicjalizujesz nwd jako 0 a potem, po pętli sprawdzasz czy nadal jest tam 0, jeżeli tak to oznacza że NWD nie istnieje.

Dobrze by było aby warunek w pętli był <= Min(n, m).

2

Ładniej i przejrzyściej to w funkcji będzie wyglądać:

 public static int gcd(int a, int b){
    while (b != 0){
      int m = b;
      b = a % b;
      a = m;
    }
    return a;
  }
0

Napisałam tak:

public class NajwiekszyWspolnyDzielnik {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("Wprowadz pierwsza liczbe");
        int n = input.nextInt();
        System.out.println("Wprowadz druga liczbe");
        int m = input.nextInt();
        int nwd = 0;
        for (int i=1; i<=m; i++){
            if (((m%i)==0) && ((n%i)==0)) nwd = i;


        }
        System.out.println("Najwiekszy wspólny dzielnik jest rowny" + " " + nwd);
    }
}

I wszystko działa ! Dziękuje wam bardzo!! Mam jeszcze małe pytanie. Czy jest różnica gdy tak jak mam w tym przykładzie przypisuje do nwd wartość 1 albo 0? Czy to wychodzi na to samo czy w różnych przypadkach przypisuje się 1 a w innych 0?

1

Nie ma różnicy bo i tak przy pierwszej iteracji pętli zostanie zmienione na 1, a potem na wspólny dzielnik (jeżeli takowy istnieje).

0

Okej dziękuję wam bardzo!

1 użytkowników online, w tym zalogowanych: 0, gości: 1