Optimized Prime Number Check

Welcome to your first lesson! We're kicking off your journey into competitive programming by building a solid foundation in number theory. This is a crucial topic that appears frequently in programming contests, and mastering its fundamentals will be a significant step in your strategy for improving.

This lesson begins our first module, "Core Number Theory: Primes and Divisibility." Our goal today is to tackle a fundamental problem: how to determine if a given number is prime. We'll start with a simple idea and refine it into an efficient algorithm that runs in O(sqrt(n)) time—a technique you'll use constantly.

What is a Prime Number?

Before we write any code, let's be precise about our terms. What exactly is a prime number? It's a question with a common, but slightly flawed, answer.

To see a clear and correct definition, watch the beginning of this video from the "take U forward" channel.

L3. Check if a Number if Prime or not | Maths Playlist

This video starts by clarifying the definition of a prime number, which is a perfect starting point.

Watch the segment from the definition, where the presenter explains why "a number divisible by 1 and itself" is an incomplete definition and provides the correct one.

As you just saw, the precise definition is: A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. This distinction is vital for handling edge cases like the number 1, which has only one divisor and is therefore not prime.

A First Attempt: The Naive Approach

The most direct way to check if a number n is prime is to test every possible divisor. Based on the definition, we don't need to check 1 or n, as they will always be divisors. We can simply check all integers from 2 up to n-1. If any of these numbers divide n evenly, we've found a factor other than 1 and n, so n cannot be prime.

This approach is often called the "brute-force" or "naive" method. For a quick overview of this idea, please read the first part of this GeeksforGeeks article.

Trial division Algorithm for Prime Factorization - GeeksforGeeks

This article introduces the naive approach and analyzes its complexity before moving on to the optimized version.

Read the section titled Naive Approach. Pay attention to the pseudocode and the time complexity analysis.

As the article explains, this algorithm has a time complexity of O(N). For small numbers, this is fine. But in competitive programming, N can be very large, often up to $1 0^{9}$ or even $1 0^{12}$ . An O(N) algorithm would be far too slow in these cases, leading to a "Time Limit Exceeded" (TLE) error. We need a better way.

The Key Insight: Divisors Come in Pairs

The path to a faster algorithm lies in a simple but powerful observation about how divisors work. Let's think about the divisors of 36:
1, 2, 3, 4, 6, 9, 12, 18, 36

We can group them into pairs that multiply to 36:

(1, 36)
(2, 18)
(3, 12)
(4, 9)
(6, 6)

Notice that for each pair (a, b) such that a * b = n, if a is small, b is large. They meet in the "middle," around the square root of n ( $36 = 6$ ). In every pair, one of the divisors is less than or equal to $n$ , and the other is greater than or equal to $n$ .

This means that if a number n has a divisor, it must have one that is less than or equal to its square root. Therefore, we don't need to check for divisors all the way up to n-1. We only need to check up to $n$ .

The following video from CodeNCode provides an excellent, step-by-step proof of this crucial concept.

L01 : Primality Test in O(sqrt(N)) Time | Number Theory | CodeNCode

This video builds the intuition for the sqrt(N) optimization by explaining divisor pairs and then formally proving why the optimization works.

First, watch the explanation on divisor pairs. Then, carefully follow the proof by contradiction that establishes why one factor must be less than or equal to \sqrt{n}.

The O(sqrt(n)) Algorithm: Trial Division

This insight leads us directly to the optimized algorithm, known as Trial Division. To test if n is prime:

Handle the base cases: numbers less than 2 are not prime.
Iterate from d = 2 up to $n$ .
In each iteration, check if d divides n (n % d == 0).
If a divisor is found, we can immediately conclude n is not prime and stop.
If the loop finishes without finding any divisors, n must be prime.

This "wall" at $n$ , beyond which we don't need to search, is the source of our efficiency gain.

This diagram illustrates the concept of trial division. We only need to test for divisors up to the 'WALL', which is placed at $\sqrt{n}$. If no divisors are found before hitting the wall, the number is prime.

Now, let's look at a clean C++ implementation of this algorithm, which is standard practice in competitive programming.

Primality tests

CP-Algorithms is a fantastic resource for competitive programmers. This page gives a concise explanation and an idiomatic C++ implementation.

Read the section Trial division. Focus on the provided C++ code. bool isPrime(int x) { for (int d = 2; d * d <= x; d++) { if (x % d == 0) return false; } return x >= 2; } Notice the loop condition d * d <= x. This is a common and effective way to check d <= sqrt(x) without using floating-point arithmetic from the <cmath> library. Integer multiplication is generally faster and avoids potential precision issues with sqrt(). The final return x >= 2; elegantly handles cases like 0, 1, and negative numbers, ensuring they are correctly identified as not prime.

The Impact of Optimization

The time complexity of the trial division algorithm is O(sqrt(n)) because the loop runs approximately $n$ times. How much better is this?

Let's say N = 1,000,000,000 (10⁹).

O(N) approach: Requires about 10⁹ operations. This will take several seconds and result in TLE.
O(sqrt(N)) approach: Requires about $1 0^{9} \approx 31, 622$ operations. This is instantaneous.

The difference in performance is dramatic, as shown in this graph.

This graph compares the growth rates of O(N) and O(sqrt(N)). The O(N) function grows linearly and rapidly becomes very large, while the O(sqrt(N)) function grows much more slowly, making it far more efficient for large inputs.

This optimization is not just a minor tweak; it's the difference between a solution that passes and one that fails.

Summary and Next Steps

In this lesson, you've learned a fundamental algorithm in any competitive programmer's toolkit. Here are the key takeaways:

A prime number is a natural number greater than 1 with exactly two divisors: 1 and itself.
The naive primality test runs in O(N) time, which is too slow for large inputs.
The key optimization comes from the fact that if n has a divisor, it must have one that is less than or equal to $n$ .
The Trial Division algorithm uses this insight to check for primality in O(sqrt(n)) time, which is highly efficient for single number checks.

You now have an effective method for determining if a single number is prime. But what if a problem asks you to find all prime numbers up to a given limit N? Running our O(sqrt(n)) test for every number up to N would be too slow if N is large.

In our next lesson, we will explore a completely different and remarkably efficient technique for this exact problem: the Sieve of Eratosthenes.