Chiński Test Pierwszości
Kod był wyświetlany 1715 razy.
    /*
  Name: Chiński Test Pierwszości
  Copyright: GPL GNU
  Author: Radek Szczygiel
  Date: 27-11-08 15:37
  Description: Algorytm testuje czy dana liczba jest pierwsza.
*/

#include <iostream>
using namespace std;

int main()
{
   unsigned long long n=0,tmp=0,result=1;   //rezerwujemy zmienne na potrzebne obliczenia
   unsigned long long i=0,j=0;
   short int word [(sizeof(n))+1] = {0};   //tablica ktora przechowuje binarna postc podanej liczby (w odwotnej kolejnosci)

   cout<<"Podaj liczbe do sprawdzenia !"<<endl;
   cin>>n;
   tmp=n;

   if(n==2)                                 //jeśli n==2 to odrazu wypisujemy
   {
      cout<<"\nTAK";
      cin.ignore();
      getchar();
      return 0;
   }


   while(tmp>=1)                                                               //dzielimy liczbe na postac binarna
   {
       word[i]=tmp%2;
       tmp/=2;
       i++;
   }

   unsigned long long *reszta = new unsigned long long [i+1];                  //deklarujemy tablice na przechowywanie reszt
   reszta[0]=2;

   for(j=1;j<=i;j++)                                                           //liczmy reszty
       reszta[j]=((reszta[j-1]%n)*(reszta[j-1]%n))%n;

   for(j=0;j<=i;j++)                                                           //wyliczamy koncowy rezultat
       if(word[j]==1)
           result*=reszta[j];

    result%=n;

    if(result==2)                                                               //wypisujemy rezultat na ekranie
        cout<<"TAK";
    else
        cout<<"NIE";

    cout<<endl;

    cin.ignore();
    getchar();
    return 0;
}


    
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT