import java.util.Random;

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


public class Miller_Rabin {

	private static final 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 };
	
//	 calculates a^b mod m
	private static int power_modulo_fast(int a, int b, int m)
	{
	   int i;
	   int 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 result;
	}

//	Miller-Rabin test
//	retrun: true - probably prime
//	        false - not prime
//	
	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.nextInt(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;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		   int n, k;

		   System.out.println("Podaj liczbe do sprawdzenia.");
		   n = Console.readInt("");

		   System.out.println("Podaj dokladnosc sprawdzenia.");
		   k = Console.readInt("");

		   if (MillerRabin(n, k))
		   {
			   System.out.println("Liczba jest prawdopodobnie pierwsza.");
		   }
		   else
		   {
			   System.out.println("Liczba jest zlozona.");
		   }
	}

}