Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Primality Check

EASYProblemSolveExternal Links

Description

Given a positive integer n, determine whether n is a prime number or not.

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In other words, a prime number n can only be divided evenly (with zero remainder) by exactly two numbers: 1 and n.

For example, 7 is prime because the only numbers that divide it are 1 and 7. However, 6 is not prime because it can be divided by 2 and 3 (in addition to 1 and 6) — so 6 has more than two divisors.

The first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

Note that 1 is NOT a prime number — by definition, primes must be greater than 1. Also, 2 is the only even prime number, since every other even number is divisible by 2.

Return true if n is prime, and false otherwise.

Examples

Example 1

Input: n = 17

Output: true

Explanation: We need to check whether any number between 2 and 16 divides 17 evenly:

  • 17 % 2 = 1 ✗
  • 17 % 3 = 2 ✗
  • 17 % 4 = 1 ✗
  • ... (no number from 2 to 16 divides 17)
  • 17 % 16 = 1 ✗

No divisor found other than 1 and 17 itself. Therefore 17 is prime.

Example 2

Input: n = 56

Output: false

Explanation: We check if any number between 2 and 55 divides 56:

  • 56 % 2 = 0 ✓ → 2 divides 56!

Since we found a divisor other than 1 and 56, the number 56 is NOT prime. We can stop immediately — finding even one extra divisor is enough to conclude the number is composite (not prime).

Example 3

Input: n = 1

Output: false

Explanation: By definition, prime numbers must be greater than 1. The number 1 has only one divisor (itself), not two. So 1 is not prime. This is an important edge case to handle before any divisibility checking.

Constraints

  • 1 ≤ n ≤ 10^9

Editorial

Brute Force

Intuition

The most natural way to check if a number is prime is to follow the definition directly: a prime number has no divisors other than 1 and itself.

So we can try dividing n by every integer from 2 to n-1. If any of these numbers divides n evenly (remainder is zero), then n has an extra divisor and is NOT prime. If none of them divide n, then the only divisors are 1 and n — so n is prime.

Think of it like a trial: the number n is "innocent" (prime) unless proven "guilty" (composite). We put every candidate divisor from 2 to n-1 on the witness stand. If even one of them divides n perfectly, n is found guilty — it is composite. If all candidates fail to divide n, the number is declared innocent — it is prime.

Before starting the trial, we handle the edge case: if n ≤ 1, it cannot be prime by definition, so we immediately return false.

Step-by-Step Explanation

Let's trace through with n = 29:

Step 1: Check the edge case: is n ≤ 1? No (29 > 1), so we proceed.

Step 2: Start with i = 2. Is 29 % 2 == 0? No (remainder = 1). 2 does not divide 29. Move on.

Step 3: i = 3. Is 29 % 3 == 0? No (remainder = 2). Move on.

Step 4: i = 4. Is 29 % 4 == 0? No (remainder = 1). Move on.

Step 5: i = 5. Is 29 % 5 == 0? No (remainder = 4). Move on.

Step 6: Continue checking i = 6 through i = 13. None divide 29.

Step 7: i = 14. Is 29 % 14 == 0? No (remainder = 1). Move on.

Step 8: Continue checking i = 15 through i = 28. None divide 29 evenly.

Step 9: We have exhausted all candidates from 2 to 28, and none divided 29. The only divisors of 29 are 1 and 29 itself.

Result: 29 is prime. But notice: we performed 27 divisibility checks, and none were successful. For a large prime like 999999937, we would need over 999 million checks!

Brute Force — Checking Every Number from 2 to n-1 — Watch how we try dividing 29 by every candidate from 2 to 28. Since 29 is prime, every single check fails — demonstrating the worst case for brute force.

Algorithm

  1. If n ≤ 1, return false (not prime by definition)
  2. Iterate i from 2 to n-1:
    • If n % i == 0, return false (found a divisor, so n is composite)
  3. If no divisor was found, return true (n is prime)

Code

#include <iostream>
using namespace std;

bool isPrime(int n) {
    // Edge case: numbers <= 1 are not prime
    if (n <= 1) return false;
    
    // Check every number from 2 to n-1
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;  // Found a divisor, not prime
        }
    }
    
    return true;  // No divisor found, n is prime
}

int main() {
    cout << isPrime(29) << endl;  // Output: 1 (true)
    cout << isPrime(56) << endl;  // Output: 0 (false)
    cout << isPrime(1) << endl;   // Output: 0 (false)
    return 0;
}
def is_prime(n: int) -> bool:
    # Edge case: numbers <= 1 are not prime
    if n <= 1:
        return False
    
    # Check every number from 2 to n-1
    for i in range(2, n):
        if n % i == 0:
            return False  # Found a divisor, not prime
    
    return True  # No divisor found, n is prime

print(is_prime(29))   # Output: True
print(is_prime(56))   # Output: False
print(is_prime(1))    # Output: False
public class PrimalityCheck {
    public static boolean isPrime(int n) {
        // Edge case: numbers <= 1 are not prime
        if (n <= 1) return false;
        
        // Check every number from 2 to n-1
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                return false;  // Found a divisor, not prime
            }
        }
        
        return true;  // No divisor found, n is prime
    }
    
    public static void main(String[] args) {
        System.out.println(isPrime(29));   // Output: true
        System.out.println(isPrime(56));   // Output: false
        System.out.println(isPrime(1));    // Output: false
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case (when n is prime), we iterate from 2 to n-1, performing n-2 modulo operations. For a composite number, we might exit early when the first divisor is found (e.g., even numbers exit at i=2), but the worst case is always a prime number where every single candidate must be checked. For n = 10^9, this means roughly a billion iterations.

Space Complexity: O(1)

We only use a single loop variable i. No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force checks every number from 2 to n-1. When n is prime (the worst case), we perform n-2 modulo operations. For n = 10^9, that is nearly one billion iterations — taking several seconds and exceeding typical time limits.

But consider what happens when we find a divisor. If some number d divides n (where 2 ≤ d ≤ n-1), then n/d is also a divisor. These divisors come in pairs: (d, n/d). Critically, in every such pair, at least one divisor must be ≤ √n.

Here is the reasoning: if both d and n/d were greater than √n, then d × (n/d) would be greater than √n × √n = n. But d × (n/d) = n, so we have a contradiction. Therefore, at least one factor in every pair is ≤ √n.

This means: if n has ANY divisor other than 1 and itself, at least one such divisor is ≤ √n. We do not need to check beyond √n!

For n = 10^9, √n ≈ 31,623. Instead of checking nearly a billion candidates, we only need to check about 31,623 — a speedup of over 30,000×.

Optimal Approach - Trial Division up to √n

Intuition

The key insight is based on the pairing property of divisors: if n = a × b, then one of a or b must be ≤ √n.

Imagine you are guarding a gate and need to verify that no unwanted visitor (divisor) exists. Instead of checking every person in a city of n residents (2 through n-1), you realize that divisors always arrive in pairs. If one partner in the pair is tall (> √n), the other must be short (≤ √n). So you only need to check the short side — everyone up to √n. If no short divisor exists, no tall divisor exists either, because they cannot exist alone.

So we iterate i from 2 to √n. If n % i == 0 for any i in this range, n is composite. If no such i exists, n is prime.

We can also handle small cases efficiently:

  • If n ≤ 1: not prime
  • If n == 2 or n == 3: prime (the smallest primes)
  • If n is divisible by 2 or 3: not prime

After handling these, all remaining primes are of the form 6k ± 1 (i.e., one less or one more than a multiple of 6). This is because every integer is of the form 6k, 6k+1, 6k+2, 6k+3, 6k+4, or 6k+5. Among these, 6k is divisible by 6, 6k+2 and 6k+4 are divisible by 2, and 6k+3 is divisible by 3. So primes greater than 3 can only be 6k+1 or 6k+5 (which is the same as 6k-1).

Using this, we check divisibility by 2 and 3 first, then only check candidates of the form 6k ± 1, effectively skipping two-thirds of all candidates. This is the standard optimized trial division approach.

Step-by-Step Explanation

Let's trace through with n = 221 (√221 ≈ 14.87):

Step 1: Check edge cases: Is n ≤ 1? No. Is n == 2 or n == 3? No.

Step 2: Check divisibility by 2: Is 221 % 2 == 0? No (221 is odd). Move on.

Step 3: Check divisibility by 3: Is 221 % 3 == 0? No (2+2+1 = 5, not divisible by 3). Move on.

Step 4: Now check candidates of the form 6k ± 1, starting with i = 5. Check i = 5: Is 221 % 5 == 0? No (remainder = 1). Check i + 2 = 7: Is 221 % 7 == 0? No (remainder = 4). Move on.

Step 5: i = 11 (next 6k-1). Check 221 % 11 = 0? No (remainder = 1). Check i + 2 = 13: Is 221 % 13 == 0? Yes! 221 / 13 = 17.

Step 6: We found a divisor! 13 divides 221 (13 × 17 = 221). Since 13 ≤ √221 ≈ 14.87, we caught it within our √n range.

Result: 221 is NOT prime (it equals 13 × 17). We only checked 6 candidates (2, 3, 5, 7, 11, 13) instead of the brute force's 219 candidates (2 through 220).

Now let's also trace n = 29 (√29 ≈ 5.39) to see a prime case:

Step 1: Edge cases: 29 > 3, proceed.

Step 2: 29 % 2 = 1 → not divisible by 2.

Step 3: 29 % 3 = 2 → not divisible by 3.

Step 4: i = 5. Check 5: 29 % 5 = 4 → no. Since i = 5 and 5² = 25 ≤ 29, check i + 2 = 7: but 7² = 49 > 29, so we'd stop after checking 5.

Step 5: Actually, since i starts at 5 and i * i = 25 ≤ 29, we check 5 (no) and 7 (7*7=49 > 29 so the loop condition fails before checking 7). Loop ends.

Result: No divisor found up to √29. Therefore 29 IS prime. Only 3 actual divisibility checks (2, 3, 5) instead of 27!

Optimal — Trial Division up to √n with 6k±1 Optimization — Watch how we check only a handful of candidate divisors for n=221. Instead of checking 219 candidates, we check just 6 — and find that 13 divides 221.

Algorithm

  1. If n ≤ 1, return false
  2. If n == 2 or n == 3, return true (smallest primes)
  3. If n % 2 == 0 or n % 3 == 0, return false (divisible by 2 or 3)
  4. Iterate i from 5 while i × i ≤ n, incrementing by 6 each iteration:
    • If n % i == 0, return false (found a divisor of the form 6k-1)
    • If n % (i + 2) == 0, return false (found a divisor of the form 6k+1)
  5. If no divisor was found, return true (n is prime)

Code

#include <iostream>
using namespace std;

bool isPrime(int n) {
    // Edge cases
    if (n <= 1) return false;
    if (n <= 3) return true;  // 2 and 3 are prime
    
    // Eliminate multiples of 2 and 3
    if (n % 2 == 0 || n % 3 == 0) return false;
    
    // Check candidates of the form 6k ± 1
    // All primes > 3 are of this form
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    
    return true;
}

int main() {
    cout << isPrime(29) << endl;   // Output: 1 (true)
    cout << isPrime(221) << endl;  // Output: 0 (false, 13*17)
    cout << isPrime(1) << endl;    // Output: 0 (false)
    cout << isPrime(2) << endl;    // Output: 1 (true)
    return 0;
}
def is_prime(n: int) -> bool:
    # Edge cases
    if n <= 1:
        return False
    if n <= 3:
        return True  # 2 and 3 are prime
    
    # Eliminate multiples of 2 and 3
    if n % 2 == 0 or n % 3 == 0:
        return False
    
    # Check candidates of the form 6k ± 1
    # All primes > 3 are of this form
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    
    return True

print(is_prime(29))    # Output: True
print(is_prime(221))   # Output: False (13*17)
print(is_prime(1))     # Output: False
print(is_prime(2))     # Output: True
public class PrimalityCheckOptimal {
    public static boolean isPrime(int n) {
        // Edge cases
        if (n <= 1) return false;
        if (n <= 3) return true;  // 2 and 3 are prime
        
        // Eliminate multiples of 2 and 3
        if (n % 2 == 0 || n % 3 == 0) return false;
        
        // Check candidates of the form 6k ± 1
        // All primes > 3 are of this form
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        
        return true;
    }
    
    public static void main(String[] args) {
        System.out.println(isPrime(29));    // Output: true
        System.out.println(isPrime(221));   // Output: false (13*17)
        System.out.println(isPrime(1));     // Output: false
        System.out.println(isPrime(2));     // Output: true
    }
}

Complexity Analysis

Time Complexity: O(√n)

The loop runs from i = 5 while i × i ≤ n. Since i increments by 6 each iteration, the number of iterations is approximately √n / 6. Each iteration performs two modulo operations (checking i and i+2). In Big-O terms, this simplifies to O(√n). For n = 10^9, we perform roughly √(10^9) / 3 ≈ 10,541 modulo operations — a massive improvement over the brute force's billion operations.

For composite numbers, the function returns even faster: as soon as the first divisor is found, we exit immediately. Only prime numbers require the full √n scan.

Space Complexity: O(1)

We only use a single loop variable i and a few comparisons. No additional data structures are needed regardless of the input size.