Is prime

Return true if n is a prime number — a whole number greater than 1 whose only divisors are 1 and itself.

isPrime(n)

Examples

isPrime(2)   // → true
isPrime(7)   // → true
isPrime(1)   // → false   (1 is not prime)
isPrime(12)  // → false   (12 = 2 × 6)

Walkthrough

Thinking it through

A number is prime if nothing but 1 and itself divides it evenly. The obvious way to check that: try every number from 2 up to n-1 and see if any divide evenly. That works, but it's way more checking than you actually need.

Handling the edge cases first

Get the boundaries right before anything else. Numbers less than 2 — 0, 1, and negatives — are never prime, by definition. Rule those out immediately instead of letting a loop stumble through them.

The key insight: factors come in pairs

If a number n has a divisor d, it also has a partner divisor n / d, since d * (n/d) = n. One of that pair is always ≤ the square root of n, and the other is always ≥ it — they straddle the square root. Take 100: its square root is 10. The divisor pairs are (2, 50), (4, 25), (5, 20), (10, 10) — in every pair, one side is 10 or less.

So if you check every candidate divisor up to the square root and find nothing, there's no divisor hiding further out either — its partner would already have shown up in your search range.

Building the approach

Rule out numbers less than 2 right away.
Try each candidate divisor starting at 2, checking whether it divides n evenly.
Stop once your candidate, multiplied by itself, exceeds n — that's the same as "candidate exceeds the square root of n," without needing a square root function.
Found a divisor? Not prime. Made it through the whole range without one? Prime.

Why this is a big deal

For n = 1,000,000, checking every number up to a million is a lot of work. Checking only up to the square root means checking up to 1,000 instead — a thousand times less. The bigger the number, the bigger that gap gets. Whenever you see factors pairing up around a square root, that's your cue to cut the search space from linear down to roughly its square root.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.