#include <iostream>
#include <string>
#include <random>


using namespace std;




bool IsPrime(long long numar)
{

	if ((numar & 1) == 0)
	{
		if (numar == 2)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	long long num = (long long)sqrt(numar);

	for (int i = 2; i <= num; i += 1)
	{
		if ((numar % i) == 0)
		{
			return false;
		}
	}
	return true;
}

 bool IsMersennePrime(long long n)
{

	 long long x = (long long ) (pow(2, n) - 1);


//	 return true;
	return IsPrime((long long)x);
}


 void job_1()
 {
	 for (long long i = 2; i <= 257; i++)
	 {
		 if (IsMersennePrime(i))
			 cout << "Nr prim: " << i << "\tMersenne Prime: " << (long long)(pow(2, i) - 1) << endl;
	 }
 }


 void job_2(int number)
 {
	 int i = 1, u = 1, sum = 0, ctr = 0;

	 while (i <= number)
	 {
		 while (u <= number)
		 {
			 if (u<i)
			 {
				 if (i%u == 0)
					 sum = sum + u;
			 }
			 u++;
		 }
		 if (sum == i)
		 {
			 ctr++;
			 cout << i << " is a Perfect number." << "\n";
		 }
		 i++;
		 u = 1;  sum = 0;
	 }
	 cout << "Perfect numbers from 1 to "<<number <<" (count): "<< ctr << "\n";
 }


 string job_3(int p)
 {
	 int s = 4;
	 long M = (long)pow(2,p)-1;

	 for (int i = 3; i< p; i++)
	 {
		 s = ( s*s - 2) % M;
	 }

	 return  (s == 0) ?  "Prime" : "Composite";

 }


 bool MillerTest(int n, int d)
 {

	 std::random_device rd; // obtain a random number from hardware
	 std::mt19937 eng(rd()); // seed the generator
	 std::uniform_int_distribution<> distr(2, n-2); // define the range

	 int a = distr(eng);

	 long x = (long) pow(a,d) % n;

	 if (x == 1 || x == n - 1)
	 {
		 return true;
	 }


	 while (d != n-1)
	 {
		 x = (x * x) % n;
		 if (x == 1)
		 {
			 return false;
		 }

		 if (x == n-1)
		 {
			 return true;
		 }

	 }

 }

 bool isPrime(int n, int k)
 {
	 // Corner cases
	 if (n <= 1 || n == 4)  return false;
	 if (n <= 3) return true;

	 // Find r such that n = 2^d * r + 1 for some r >= 1
	 int d = n - 1;
	 while (d % 2 == 0)
		 d /= 2;

	 // Iterate given nber of 'k' times
	 for (int i = 0; i < k; i++)
	 if (MillerTest(d, n) == false)
		 return false;

	 return true;
 }



 void job_4()
 {
	 int k = 4;  // Number of iterations

	 cout << "All primes smaller than 100: \n";
	 for (int n = 1; n < 100; n++)
	 if (isPrime(n, k))
		 cout << n << " ";
 }


int main()
{

	cout << "Job 1: Write a prime generator using Mersene rules"<<endl<<endl;
	job_1();

	cout << endl <<"Job 2: Write a perfect numbers generator " << endl << endl;
	job_2(10000);

	cout << endl << "Job 3: Write a prime number generator using Lucas-Lehmer Test " << endl << endl;
	cout << endl << "For p = 34 => "<<job_3(34) << endl;

	cout << endl << "Job 4: Write a prime number generator using Miller-Rabin test" << endl << endl;
	job_4();












	return 0;
}