// MethodsExamples.java

// Here are some examples of some Java methods which
// we wrote today (2-feb-05) in "Math with Java".

// Carpe diem.  :-)

class MethodsExamples {

	// public static RETURN_TYPE  NAME( TYPE1 ARG1, TYPE2 ARG2, ... ) {
	//	BODY
	// }

	public static boolean isDivisibleBy(int n, int k) {
		return (n % k == 0);
	}
	
	public static boolean isPrime(int n) {
		int counter;
		if (n < 2)
			return false;
		for (counter=2; counter<n; counter++) {
			if (isDivisibleBy(n,counter))
				return false;
		}
		return true;
	}
	
	public static boolean fasterIsPrime(int n) {
		int counter;
		if (n < 2)
			return false;
		if (n == 2)
			return true;
		if (isDivisibleBy(n,2))
			// it's even so it's not prime
			return false;
		int maxCounter = (int)Math.sqrt(n);
		for (counter=3; counter<=maxCounter; counter = counter + 2) {
			if (isDivisibleBy(n,counter))
				return false;
		}
		return true;
	}

	public static int factorial(int n) {
		int result = 1;
		int counter;
		for (counter = 2; counter <= n; counter++) {
			result = result * counter;
		}
		return result;
	}

	// n-choose-k = n! / (k! (n-k)!)	
	public static int nChooseK(int n, int k) {
		int result = factorial(n) / (factorial(k) * factorial(n-k));
		return result;
	}

	public static void main(String[] args) {
		int n = 10000019; // readInt();
		for (int i=0; i<20; i++)
			System.out.println("using fasterIsPrime: " + fasterIsPrime(n));
		for (int i=0; i<20; i++)
			System.out.println("using isPrime: " + isPrime(n));
		
		for (n = 10000000; true; n++)
			if (fasterIsPrime(n)) { System.out.println(n); return; }
	}

	///////////////////////////////////
	// readString, readInt, readDouble
	///////////////////////////////////
	
	public static String readString() {
		java.io.InputStreamReader isr = new java.io.InputStreamReader(System.in);
		java.io.BufferedReader d = new java.io.BufferedReader(isr);
		try { return d.readLine(); } catch (Exception e) { return "error"; }
	}
	public static int readInt() { return Integer.parseInt(readString()); }
	public static double readDouble() {
		return Double.valueOf(readString()).doubleValue();
	}
}