Rozkład na czynniki pierwsze.

Program, który wczyta dwie liczby naturalne i sprawdzi czy mają one takie same czynniki pierwsze (niekoniecznie w takiej samej ilości). Np. dla liczb 60 = 2235 i 90=2335 odpowiedź ma być "TAK". Wrzucam co do tej pory napisalam, da sie to jakos poprawic ?

#include <stdio.h>
int main () {
    int n, m;
    printf ("Podaj dwie liczby naturalne:");
    scanf("%d", &n, &m);


    int nwd(int a, int b){
    int c;
    while (b != 0)
    {
        c = a % b;

        a = b;
        b = c;
    }
    return a;
}
    int x = nwd(n, m);
        while (x != 1){
        n = n/x;
        x = nwd(n, x);

}
    if (n == 1){
        printf("TAK");
        }
    else {
        printf("NIE");
        }
}

Po pierwsze wyrzuć funkcję NWD poza main()
po drugie starczy sam NWD bez dodatkowych zabiegów, jeśli będzie większy niż 1 to mają.

1. Wyciągnij to NWD w dobre miejsce żeby kod sie kompilował.
2. Wyciągasz NWD, dzielisz obie liczby przez to NWD ale wielokrotnie, tzn dopóki któraś dzieli sie bez reszty (żeby od razu pozbyć się wielokrotnych pierwiastków)
3. Jeśli na koniec zostaną ci dwie 1 to znaczy że TAK, w innym wypadku NIE.

Może tak (dane to a i b):

1. szukamy najmniejszego czynnika pierwszego liczby a - oznaczmy go c
2. jeśli b nie dzieli się przez c to NIE
3. dzielimy a i b przez dopóki się da
4. jeśli otrzymany dwie jedynki, to TAK
5. szukamy najmniejszego czynnika pierwszego liczby a większego niż c
   ...

@bogdans dość ryzykowne bo jak dostaniesz np. do zbadania jakieś duże liczby które są np. iloczynem 2 liczb pierwszych albo w ogole same są pierwsze to sie będzie liczyc do końca świata. Pomysł z NWD nie jest zły bo potencjalnie da nam znacznie mniejszy czynnik do faktoryzacji. Jeśli już to faktoryzowałbym NWD(a,b) a nie samo a albo b.

Wyszło mi coś takiego:
#include <stdio.h>

int nwd(int a, int b){
int c;
while (b != 0)
{
    c = a % b;

    a = b;
    b = c;
}
return a;

}

int main () {
int n, m, k, l;
printf ("Podaj dwie liczby naturalne:");
scanf("%d", &n, &m);

int x = nwd(n, m);
while (m >= x && m%x == 0){
m = m/x;
}
while (n >= x && n%x == 0){
n = n/x;
}
for (k = 2; k < (x/2); k++) {
while (n%k == 0){
n = n/k;
}
for (l = 2; l < (x/2); l++)
while (m%l == 0){
m = m/l;
}
}
if (n == 1 && m == 1){
printf("TAK");
}
else {
printf("NIE");
}
}