/*
  Sketch: teilerfremd
  Datum: 14.04.2024
  Zweck: sind zwei Zahlen teilerfremd oder nicht?
  Autor: MIWIS
*/

unsigned long a = 105;
unsigned long b = 56;

void setup() {
  Serial.begin(115200);
  Serial.println("***Programm startet***");
  if (teilerfremd(a, b)) {
    Serial.print(a);
    Serial.print(" und ");
    Serial.print(b);
    Serial.println(" sind teilerfremd");
  } else {
    Serial.print(a);
    Serial.print(" und ");
    Serial.print(b);
    Serial.println(" haben einen gemeinsamen Teiler");
  }
  Serial.println("***Programm beendet***");
}

void loop() {
}

unsigned long teilerfremd(unsigned long a, unsigned long b) {
  unsigned long rest;
  //Serial.print(a);
  //Serial.print(" ");
  //Serial.println(b);
  //Euklidischer Algorithmus ggT
  while (1) {
    // a % b bedeutet den Teilerrest von a / b (Modulo)
    rest = a % b;
    a = b;
    b = rest;
    //Serial.println(b);
    // b=1 => teilerfremd, b=0 => nicht teilerfremd (0=>falsch)
    if (b < 2) {
      return (b);
    }
  }
}