bool isPrime(int n)//фунция за проверка дали едно число е просто
{

	if (n <= 1)  return false;
	if (n <= 3)  return true;


	if (n % 2 == 0 || n % 3 == 0) return false;

	for (int i = 5; i*i <= n; i = i + 6)
		if (n%i == 0 || n % (i + 2) == 0)
			return false;

	return true;
}


int power(int x, unsigned int y, int p)
{
	int s = 1;

	x = x % p;

	while (y > 0)
	{

		if (y & 1)
			s = (s*x) % p;

		y = y >> 1;
		x = (x*x) % p;
	}
	return s;
}
void findPrimefactors(unordered_set<int> &s, int n)
{

	while (n % 2 == 0)
	{
		s.insert(2);
		n = n / 2;
	}

	for (int i = 3; i <= sqrt(n); i = i + 2)
	{

		while (n%i == 0)
		{
			s.insert(i);
			n = n / i;
		}
	}


	if (n > 2)
		s.insert(n);
}
int CheckFor_PR(int n) //изпълнение на задача 11 проверка за примитивен корен
{
	unordered_set<int> s;


	if (isPrime(n) == false)
		return false;


	int p = n - 1;


	findPrimefactors(s, p);


	for (int r = 2; r <= p; r++)
	{

		bool flag = false;
		for (auto it = s.begin(); it != s.end(); it++)
		{


			if (power(r, p / (*it), n) == 1)
			{
				flag = true;
				break;
			}
		}


		if (flag == false)
			return true;
	}


	return false;
}