// Test pierwszości - test Millera-Rabina
// www.algorytm.org
// Tomasz Lubinski (c) 2007

using System;

namespace miller_rabin_cs
{
	/// <summary>
	/// Miller-Rabin test
	/// </summary>
	class Miller_Rabin
	{

		private static int [] powerOf2 = {
			1<<0,  1<<1,  1<<2,  1<<3,  1<<4,  1<<5,  1<<6,
			1<<7,  1<<8,  1<<9,  1<<10, 1<<11, 1<<12, 1<<13,
			1<<14, 1<<15, 1<<16, 1<<17, 1<<18, 1<<19, 1<<20,
			1<<21, 1<<22, 1<<23, 1<<24, 1<<25, 1<<26, 1<<27,
			1<<28, 1<<29, 1<<30 };
	
		/// <summary>
		/// calculates a^b mod m
		/// </summary>
		/// <param name="a">a</param>
		/// <param name="b">b</param>
		/// <param name="m">m</param>
		/// <returns>a^b mod m</returns>
		private static int power_modulo_fast(int a, int b, int m)
		{
			int i;
			long result = 1;
			long x = a%m;

			for (i=1; i<=b; i<<=1)
			{
				x %= m;
				if ((b&i) != 0)
				{
					result *= x;
					result %= m;
				}
				x *= x;
			}

			return (int)result;
		}

		/// <summary>
		/// Miller-Rabin test
		/// </summary>
		/// <param name="n">number to check</param>
		/// <param name="k">number of checks</param>
		/// <returns>true - probably prime, false - not prime</returns>
		private static Boolean MillerRabin(int n, int k)
		{
			int s = 0;
			int s2 = 1;
			int a, d, i, r, prime;
			Random rand = new Random();

			if (n<4)
			{
				return true;
			}
			if (n%2 == 0)
			{
				return false;
			}

			// calculate s and d
			while ((s2 & (n-1)) == 0)
			{
				s  += 1;
				s2 <<= 1;
			}
			d = n/s2;

			// try k times
			for (i=0; i<k; i++)
			{
				a = rand.Next(n-1) + 1;
				if (power_modulo_fast(a, d, n) != 1)
				{
					prime = 0;
					for (r=0; r<=s-1; r++)
					{
						if (power_modulo_fast(a, powerOf2[r]*d, n) == n - 1)
						{
							prime = 1;
							break;
						}
					}
					if (prime == 0)
					{
						return false;
					}
				}
			}

			return true;
		}

		/// <summary>
		/// The main entry point for the application.
		/// </summary>
		[STAThread]
		static void Main(string[] args)
		{
		   int n, k;

		   Console.WriteLine("Podaj liczbe do sprawdzenia.");
		   n = int.Parse(Console.ReadLine());

		   Console.WriteLine("Podaj dokladnosc sprawdzenia.");
		   k = int.Parse(Console.ReadLine());

		   if (MillerRabin(n, k))
		   {
			   Console.WriteLine("Liczba jest prawdopodobnie pierwsza.");
		   }
		   else
		   {
			   Console.WriteLine("Liczba jest zlozona.");
		   }
		}
	}
}