Challenge: Prime Checker

Lab Java Intermediate 20 points

Write static boolean isPrime(int n). A prime number is bigger than 1 and can only be divided evenly by 1 and itself. Read n and print prime or not prime.

Input

One whole number n (0 ≤ n ≤ 1000000).

Output

prime or not prime.

Example

Input

Output

prime

Sample input available Sample output available

Editor

Java

Hints

0 and 1 are not prime.

Try every divisor d from 2 upwards. If n % d == 0, it's not prime.

You only need to check d while d * d <= n.

Solution explanation

If n had a divisor bigger than its square root, it would also have one smaller than it – so checking up to √n is enough.

Show solution

import java.util.Scanner;

public class Main {
    static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int d = 2; d * d <= n; d++) {
            if (n % d == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(isPrime(n) ? "prime" : "not prime");
    }
}

Output

Answer