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.

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.

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.

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

Testing every divisor from 2 to n-1 costs over two billion divisions for the largest prime input. 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

Test each candidate d from 2 to n-1 with n % d == 0 and return false at the first one that divides. This is the definition of a prime, so it is correct once you return false for n < 2.

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.

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

If d divides n, so does n / d. Both cannot be larger than √n, or their product would be larger than n. So a composite n always has a divisor at most √n: for 91 the pair is 7 and 13, and 7 ≤ 9.5. If nothing up to √n divides n, n is prime.

Write the bound as d * d ≤ n, which stays in whole numbers with no rounding. Handle 2 on its own, since an even n is prime only when it is 2. An odd n has only odd divisors, so start at 3 and step by 2. For n = 2147483647 the loop runs about 23,000 times.

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

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 and 49 then pass as primes.
Overflow in d * d. In a 32-bit int, 46341 × 46341 wraps to a negative number, so the loop runs far past √n. Use a 64-bit type for d, or compare d ≤ n / d.

Frequently asked questions3

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.

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.

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.