Challenge: Prime Checker

Lab C Intermediate 20 points

Write a function int isPrime(int n) that returns 1 if n is a prime number and 0 if not. (A prime is bigger than 1 and can only be divided by 1 and itself.) Read n and print N is prime or N is not prime.

Input

One integer n (0 ≤ n ≤ 100000).

Output

One line.

Example

Input

Output

7 is prime

Sample input available Sample output available

Editor

Hints

Numbers below 2 are not prime.

Try dividing by every d from 2 upwards; if n % d == 0 it is not prime.

You can stop once d * d > n.

Solution explanation

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

Show solution

#include <stdio.h>

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

int main() {
    int n;
    scanf("%d", &n);
    if (isPrime(n)) {
        printf("%d is prime\n", n);
    } else {
        printf("%d is not prime\n", n);
    }
    return 0;
}

Output

Answer