Facebook
From Sloppy Flamingo, 1 Year ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 119
  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.