#include <stdio.h>
#include <stdlib.h>
#include <math.h>
// sprawdzanie czy n jest postaci n=a^b , dla a>1, b>1
// funkcja zwraca true(1) jezeli n=a^b , false(0) w przeciwnym
char krok1(unsigned int n);
//znajdz najmniejsze r takie ze ord(r)(r,n) > (log2n)^2
unsigned int krok2(unsigned int n);
//funkca zwraca true(1) jezeli spelniony jest warunek 1<nwd(a,n)< n , gdzie a < r - liczba zlozona
char krok3(unsigned int r, unsigned int n);
//Funkcja sprawdza czy n<=r. Jezeli tak to liczba jest pierwsza (return 1)
char krok4(unsigned int r,unsigned int n);
//zwraca 1 jezeli liczba n jest pierwsza , 0 jezeli jest zlozona
char aksTest(unsigned n);
// funcka oblicza nwd liczb (a,b) metoda wykorzystujaca funkcje modulo
unsigned int nwd(unsigned int a, unsigned int b);

int main()
{


    unsigned int n=31;
    int x=krok2(n);
    printf("Szukane r to:%d\n",x);
    getchar();
    return 0;
}

// Tutaj da sie zrobic innym szybszym sposobem
char krok1(unsigned int n)
{
    int a,b;
    a=2;

    while(a<sqrt(n)+1)
    {
        b=2;
        while(pow(a,b<=n))
        {
            if(pow(a,b)==n)
                return 1;
            b++;
        }
        a++;

    }
    return 0;
}

unsigned int krok2(unsigned int n)
{
    char znaleziono;
    unsigned int log5n=pow(log2(n),5);
    unsigned int log2n=log2(n)*log2(n);
    for (int r=2;r<log5n;r++)
        {
            znaleziono=1; // true
            long long wynik=1;
            for(unsigned int k=1;k<log2n+1;k++)
            {
            /*wynik=n%r;
            for(int i=1;i<k;i++)
            {
                wynik=wynik*(n%r);
                printf("wynik:%d\n",wynik);
            }

            wynik=wynik%r;
            if(wynik==1)
                znaleziono=0;

            */
            if((long)(pow(n,k))%r==1)         // jak zakomentujesz tego if'a a odkomentujesz tego na gorze to dziala do 31
                znaleziono=0;

            }
            if(znaleziono==1)
                return r;
        }

}

char krok3(unsigned int r, unsigned int n)
{
    for(int a=2;a<r;a++)
    {
        unsigned int nwdAB=nwd(a,n);
        if(1<nwdAB && nwdAB<n )
            return 1;
    }
    return 0;
}

char krok4(unsigned int r, unsigned int n)
{
    if (n<=r)
        return 1;
    return 0;
}
char aksTest(unsigned n)   // 0-zlozona 1-pierwsza
{
    if(krok1(n)) 
        return 0;
    unsigned int r=krok2(n);
    if(krok3(r,n))
        return 0;
    if(krok4(r,n))
        return 1;


    return 1;

}


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

}