Introduction

Yes. For ordinary programming tasks, the simplest correct primality test is trial division up to the square root of n. It is easy to implement, easy to explain, and fast enough for moderate input sizes, even though it is not the best choice for extremely large numbers.

The Core Idea Behind the Simple Test

A number greater than 1 is prime if it has no positive divisors other than 1 and itself. The important optimization is that you do not need to test every number below n.

If n is composite, then n = a * b for some integers a and b. At least one of those factors must be less than or equal to sqrt(n). Once you have checked all possible divisors up to that boundary, there is no reason to keep going.

A Straightforward Python Implementation

1def is_prime(n: int) -> bool:
2    if n < 2:
3        return False
4    if n in (2, 3):
5        return True
6    if n % 2 == 0:
7        return False
8
9    divisor = 3
10    while divisor * divisor <= n:
11        if n % divisor == 0:
12            return False
13        divisor += 2
14
15    return True
16
17
18for value in [0, 1, 2, 3, 4, 17, 21, 97, 99]:
19    print(value, is_prime(value))

This is a strong default when you need occasional primality checks and the inputs are not huge.

Why the Square-Root Bound Works

Suppose both factors of a composite number were greater than sqrt(n). Their product would then be greater than n, which is impossible. So every composite number must have at least one factor at or below the square-root boundary.

That fact is what turns naive divisibility checking into a practical simple algorithm.

A Slightly Smarter but Still Simple Variant

After checking divisibility by 2 and 3, you can skip many unnecessary tests by using the 6k +/- 1 pattern. Every prime greater than 3 must be of that form.

1def is_prime_6k(n: int) -> bool:
2    if n < 2:
3        return False
4    if n in (2, 3):
5        return True
6    if n % 2 == 0 or n % 3 == 0:
7        return False
8
9    k = 5
10    while k * k <= n:
11        if n % k == 0 or n % (k + 2) == 0:
12            return False
13        k += 6
14
15    return True

This reduces the number of trial divisions a bit, though the plain odd-divisor version is often easier to teach and maintain.

When a Different Algorithm Is Better

Trial division is a good answer for one number at a time. It is not the best answer for every prime-related task.

If you need many primes up to a limit, the Sieve of Eratosthenes is usually better:

1def sieve(limit: int) -> list[bool]:
2    prime = [True] * (limit + 1)
3    if limit >= 0:
4        prime[0] = False
5    if limit >= 1:
6        prime[1] = False
7
8    p = 2
9    while p * p <= limit:
10        if prime[p]:
11            for multiple in range(p * p, limit + 1, p):
12                prime[multiple] = False
13        p += 1
14
15    return prime

If you need primality checks for very large integers, especially in cryptography, you should use stronger algorithms such as Miller-Rabin and rely on mature libraries rather than handwritten trial division.

Choose Based on Input Size and Volume

A lot of code becomes worse because the author over-optimizes too early. For many applications, a square-root trial division function is the right balance of correctness and clarity.

The best algorithm is not the one with the most number-theory sophistication. It is the one that fits the actual size and number of inputs you have.

Common Pitfalls

The most common mistake is forgetting that 0 and 1 are not prime.

Another pitfall is checking divisors all the way up to n - 1 instead of stopping at the square root. Developers also often jump to clever optimizations before measuring whether the simple version is already fast enough.

Finally, if the input can be negative, remember that negative numbers are not prime in the usual sense used by these algorithms.

Summary

• A simple correct prime test is trial division up to sqrt(n).
• Reject values less than 2 and handle even numbers early.
• The square-root bound is what makes the basic algorithm practical.
• Use a sieve when you need many primes in a range.
• Use stronger algorithms or libraries for very large integers.