Is prime?

Challenge

Decide whether a number is prime using trial division up to its square root.

Task

Implement int is_prime(unsigned long n) that returns 1 if n is prime and 0 otherwise. No main — the grader calls it.

Input

One unsigned long argument n (n can be 0 up to large values like 7919).

Output

1 if n is prime, 0 if not. By convention 0 and 1 are not prime.

Example

is_prime(2)    ->   1
is_prime(4)    ->   0
is_prime(97)   ->   1
is_prime(100)  ->   0

Edge cases

• 0 and 1 return 0.
• 2 is the only even prime.

Rules

• Only trial-divide up to sqrt(n) (i*i <= n) for an efficient check.

Input format

One unsigned long argument n.

Output format

1 if n is prime, 0 otherwise (0 and 1 are not prime).

Constraints

Trial-divide only up to sqrt(n).

Starter code

int is_prime(unsigned long n) {
    /* TODO */
    return 0;
}