import java.util.Random;

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


public class Fermat {

//	 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%m;
	}

//	Fermat test
//	retrun: true - probably prime
//	        false - not prime
	private static boolean FermatTest(int n, int k)
	{
	   int a, i;
	   Random rand = new Random();
	   
	   if (n<4)
	   { 
	      return true; 
	   }

	   for (i=0; i<k; i++)
	   {
	      a = rand.nextInt(n-2) + 2;
	      if (power_modulo_fast(a, n-1, n) != 1)
	      {
	         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 (FermatTest(n, k))
		   {
			   System.out.println("Liczba jest prawdopodobnie pierwsza.");
		   }
		   else
		   {
			   System.out.println("Liczba jest zlozona.");
		   }
	}

}