Check Prime Number

Q: What is the time complexity of checking if a number is prime?

Trial division up to √n takes O(√n) time and O(1) space. For n up to 2^31-1 that is at most about 46,000 divisions, or 23,000 when you skip even divisors. Testing every divisor up to n-1 is O(n) , about two billion steps for the largest input.

Q: Why do you only check divisors up to the square root of n?

Divisors come in pairs d and n / d whose product is n . If both were larger than √n , their product would be larger than n . So every pair has a member at most √n , and if no divisor shows up by then, n is prime.

Q: Is 1 a prime number?

No. A prime has exactly two different divisors, 1 and itself, and 1 has only one. Leaving 1 out keeps every whole number's factorization into primes unique. That is why isPrime(1) returns false .

Q: Is there a faster way to test very large numbers for primality?

For one 32-bit number, trial division to √n is fast enough. For numbers with dozens of digits, programs use the Miller-Rabin test, which checks a few modular powers instead of trying divisors. To list every prime up to a limit, the Sieve of Eratosthenes beats testing each number on its own.

BeginnerMath and simulation

+10

A prime number is a whole number greater than 1 whose only divisors are 1 and itself. You get a positive integer n. Return true if n is prime and false otherwise. The number 1 is not prime.

Function

isPrime(n: integer) → boolean

ninteger: the positive integer to test
Returnsboolean: true if n is prime, false otherwise

Constraints

1 ≤ n ≤ 2³¹ - 1

Examples

Input: n = 29
Output: true
Explanation: None of 2, 3, 4 or 5 divides 29, and 6 × 6 = 36 is already past 29, so no divisor is left to find. 29 is prime.

Input: n = 1
Output: false
Explanation: A prime has exactly two divisors, 1 and itself. 1 has only one divisor, so the answer is false.

Input: n = 91
Output: false
Explanation: 91 looks prime, but 7 × 13 = 91. The divisor 7 turns up before the search passes √91 ≈ 9.5.

+15 hidden tests on Submit

Follow-up

Every prime above 3 has the form 6k-1 or 6k+1. Can you use that to test only a third of the candidate divisors?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The definition says to rule out every divisor from 2 to n-1, and for the largest prime input that is over two billion divisions. Divisors come in pairs that multiply to n, and the smaller one of each pair is at most √n. So you only search up to √n, about 23,000 odd candidates at most.

Try every divisor

Correct, but does not finish on the largest tests

Intuition

The definition gives you the algorithm. A number n ≥ 2 is prime when none of 2, 3, ..., n-1 divides it. Test each candidate d with n % d == 0 and return false at the first one that divides. For 91 the loop tries 2 to 6 and stops at 7.

Handle n < 2 first. For n = 1 the range of candidates is empty, so the loop would never find a divisor and would call 1 prime.

Composite numbers usually stop early, but a prime survives every test, so the loop runs to the end. For n = 2147483647, which is prime, that is about 2.1 × 10^9 divisions, far more than a few seconds allow.

Algorithm

If n < 2, return false.
Loop d from 2 to n-1.
If n % d == 0, return false.
After the loop, return true.

def isPrime(n):
    if n < 2:
        return False
    for d in range(2, n):
        if n % d == 0:
            return False
    return True

Trial division up to the square root

Intuition

Divisors come in pairs. If d divides n, so does n / d, and the two multiply to n. They cannot both be larger than √n, because then their product would be larger than n. So if n has any divisor besides 1 and itself, it has one that is at most √n. For 91 the pair is 7 and 13, and 7 ≤ 9.5. If nothing up to √n divides n, nothing above it does either.

Write the bound as d * d ≤ n instead of calling a square root function. It stays in whole numbers, with no rounding. The equal sign matters: 49 = 7 × 7, and its only divisor 7 sits exactly at √49.

You can also skip half the candidates. Handle 2 on its own: an even n is prime only when it is 2. After that an odd n has only odd divisors, so start at 3 and step by 2. For n = 2147483647 the loop now runs about 23,000 times instead of 2.1 × 10^9.

Algorithm

If n < 2, return false.
If n is even, return whether n == 2.
Start d at 3 and loop while d * d ≤ n, using a 64-bit type for d.
If n % d == 0, return false. Otherwise add 2 to d.
After the loop, return true.

def isPrime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2  # 2 is the only even prime
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

Pitfalls and edge cases

The idea fits in one line. The bugs sit at the boundaries: the smallest inputs and the last divisor.

Returning true for 1. It has one divisor, not two, so it is not prime.
Rejecting 2 because it is even. Check n == 2 before you rule out even numbers.
Looping while d * d < n instead of ≤. Squares of primes such as 9, 49 and 2147117569 = 46337² then pass as primes.
Overflow in d * d. In a 32-bit int, 46341 × 46341 = 2147488281 does not fit and wraps to a negative number, so the test keeps passing and the loop runs far past √n. Use a 64-bit type for d, or compare d ≤ n / d instead.
Taking the bound from a floating point sqrt and truncating it. A double is exact for every n here, but for 64-bit inputs rounding can land one below the true root and skip the one divisor that matters. d * d ≤ n has no such risk.

Frequently asked questions4

What is the time complexity of checking if a number is prime?

Trial division up to √n takes O(√n) time and O(1) space. For n up to 2^31-1 that is at most about 46,000 divisions, or 23,000 when you skip even divisors. Testing every divisor up to n-1 is O(n), about two billion steps for the largest input.

Why do you only check divisors up to the square root of n?

Divisors come in pairs d and n / d whose product is n. If both were larger than √n, their product would be larger than n. So every pair has a member at most √n, and if no divisor shows up by then, n is prime.

Is 1 a prime number?

No. A prime has exactly two different divisors, 1 and itself, and 1 has only one. Leaving 1 out keeps every whole number's factorization into primes unique. That is why isPrime(1) returns false.

Is there a faster way to test very large numbers for primality?

For one 32-bit number, trial division to √n is fast enough. For numbers with dozens of digits, programs use the Miller-Rabin test, which checks a few modular powers instead of trying divisors. To list every prime up to a limit, the Sieve of Eratosthenes beats testing each number on its own.