Challenge: Prime Checker

Lab C++ Intermediate 20 points

Write bool 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 integer n.

Output

prime or not prime.

Example

Input

Output

prime

Sample input available Sample output available

Editor

C++

Hints

Numbers below 2 are not prime.

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

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

Solution explanation

If a number has a divisor, one of them is at most its square root, so the loop can stop at d * d <= n.

Show solution

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n < 2) {
        return false;
    }
    for (int d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    if (isPrime(n)) {
        cout << "prime\n";
    } else {
        cout << "not prime\n";
    }
    return 0;
}

Output

Answer