1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <math.h>
4. // sprawdzanie czy n jest postaci n=a^b , dla a>1, b>1
5. // funkcja zwraca true(1) jezeli n=a^b , false(0) w przeciwnym
6. char krok1(unsigned int n);
7. //znajdz najmniejsze r takie ze ord(r)(r,n) > (log2n)^2
8. unsigned int krok2(unsigned int n);
9. //funkca zwraca true(1) jezeli spelniony jest warunek 1<nwd(a,n)< n , gdzie a < r - liczba zlozona
10. char krok3(unsigned int r, unsigned int n);
11. //Funkcja sprawdza czy n<=r. Jezeli tak to liczba jest pierwsza (return 1)
12. char krok4(unsigned int r,unsigned int n);
13. //zwraca 1 jezeli liczba n jest pierwsza , 0 jezeli jest zlozona
14. char aksTest(unsigned n);
15. // funcka oblicza nwd liczb (a,b) metoda wykorzystujaca funkcje modulo
16. unsigned int nwd(unsigned int a, unsigned int b);
17.  
18. int main()
19. {
20.  
21.  
22.     unsigned int n=31;
23.     int x=krok2(n);
24.     printf("Szukane r to:%d\n",x);
25.     getchar();
26.     return 0;
27. }
28.  
29. // Tutaj da sie zrobic innym szybszym sposobem
30. char krok1(unsigned int n)
31. {
32.     int a,b;
33.     a=2;
34.  
35.     while(a<sqrt(n)+1)
36.     {
37.         b=2;
38.         while(pow(a,b<=n))
39.         {
40.             if(pow(a,b)==n)
41.                 return 1;
42.             b++;
43.         }
44.         a++;
45.  
46.     }
47.     return 0;
48. }
49.  
50. unsigned int krok2(unsigned int n)
51. {
52.     char znaleziono;
53.     unsigned int log5n=pow(log2(n),5);
54.     unsigned int log2n=log2(n)*log2(n);
55.     for (int r=2;r<log5n;r++)
56.         {
57.             znaleziono=1; // true
58.             long long wynik=1;
59.             for(unsigned int k=1;k<log2n+1;k++)
60.             {
61.             /*wynik=n%r;
62.             for(int i=1;i<k;i++)
63.             {
64.                 wynik=wynik*(n%r);
65.                 printf("wynik:%d\n",wynik);
66.             }
67.  
68.             wynik=wynik%r;
69.             if(wynik==1)
70.                 znaleziono=0;
71.  
72.             */
73.             if((long)(pow(n,k))%r==1)         // jak zakomentujesz tego if'a a odkomentujesz tego na gorze to dziala do 31
74.                 znaleziono=0;
75.  
76.             }
77.             if(znaleziono==1)
78.                 return r;
79.         }
80.  
81. }
82.  
83. char krok3(unsigned int r, unsigned int n)
84. {
85.     for(int a=2;a<r;a++)
86.     {
87.         unsigned int nwdAB=nwd(a,n);
88.         if(1<nwdAB && nwdAB<n )
89.             return 1;
90.     }
91.     return 0;
92. }
93.  
94. char krok4(unsigned int r, unsigned int n)
95. {
96.     if (n<=r)
97.         return 1;
98.     return 0;
99. }
100. char aksTest(unsigned n)   // 0-zlozona 1-pierwsza
101. {
102.     if(krok1(n))
103.         return 0;
104.     unsigned int r=krok2(n);
105.     if(krok3(r,n))
106.         return 0;
107.     if(krok4(r,n))
108.         return 1;
109.  
110.  
111.     return 1;
112.  
113. }
114.  
115.  
116. unsigned int nwd(unsigned int a, unsigned int b)
117. {
118.     unsigned int c;
119.     while(b!=0)
120.     {
121.         c=a%b;
122.         a=b;
123.         b=c;
124.     }
125.     return a;
126.  
127. }
128.  
129.