/*
Author: MB
Version: 1.0.0, OCT 2026
Implementation Primfaktorisierung in C.
*/

#include<stdio.h>
#include<stdlib.h>

int primtest(int a){
    printf("Primtest aufgerufen mit %i \n", a);
    if ((a == 0) || (a == 1)) {
        printf("0 und 1 sind keine Primzahlen \n");
        return 0;
    }
    if (a == 2) {
        printf("2 ist eine Primzahl \n");
        return 2;
    }
    int x = 2;
    for(x = 2; x < a/2; x++){
        if(a % x == 0) {
            printf("%i ist keine Primzahl \n", a);
            return 0;
        }
    }
    printf("Naechste Primzahl %i gefunden \n", a);
    return a;
}

int nextPrime(int a){
    printf("Suche naechste Primzahl nach %i \n", a);
    int x = (a % 2 == 0)? a + 1 : a + 2;
    while (1){
        if (primtest(x)) return x;
        x = x + 2;
    }
    return 0;
}



int faktorisierung(int a, int b){
    printf("Aufruf von Faktorisierung mit %i und %i \n", a, b);
    if (a == 1){
        printf("Fertig.");
        return 1;
    }
    if (primtest(a)){
        printf("\n \t \t \t \t \t \t \t Letzter Primfaktor ist %i \n \n", a);
        return 1;
    }
    if (a % b == 0) {
        printf("\n \t \t \t \t \t \t \t Primfaktor: %i \n \n", b);
        if (a % b == 0){
            a = a / b;
            return faktorisierung(a, b);
        }
    }
    return faktorisierung(a, nextPrime(b));
}

int main(void){
    int zahl = 0;
    puts("Geben Sie eine Zahl ein: ");
    scanf("%i", &zahl);
    printf("\n");
    faktorisierung(zahl,2);
    return 1;
}