// Test pierwszości - test Fermata
// www.algorytm.org

#include<iostream>
#include<math.h>
#include<time.h>
using namespace std;

int main()
{
	srand(time(NULL)); // "zasianie ziarna"
	int k, i, p, a; // k - dokladnosc, i - zmienna pomocnicza, p - liczba do sprawdzenia, a - losowana liczba
	unsigned long long int x; // x = a^(p-1), gdzie a jest losowane w każdym obiegu
	
	cout << "Podaj liczbe do sprawdzenia: ";
	cin >> p;
	cout << "Podaj dokladnosc: ";
	cin >> k;
	
	for (i = 0; i < k; i++)
	{
		a = (rand()%(p-1))+1; // losujemy liczbe a
		x = ((unsigned long long int)pow((float)a, p-1)); // obliczamy x = a^(p-1) - uzywamy rzutowania aby doposowac typy zmiennych do definicji funkcji: float pow(float, int) - pozbywamy sie warningow
		if (x%p != 1) // obliczamy modulo
		{
			cout << "Liczba " << p << " nie jest liczba pierwsza" << endl;
			break;
		}
	}
	if (i == k) // jezeli wyszlismy z petli przez nie spelnienie warunku i < k, a nie przez break'a w ifie to liczba jest prawdopodobnie pierwsza
		cout << "Liczba " << p << " jest liczba pierwsza z dokladnoscia rowna " << k << endl;

	return 0;
}