Why Check if Number is Prime in DSA C?

The Big Idea

What if you could skip most checks and still know if a number is prime instantly?

The Scenario

Imagine you want to find out if a number is prime by checking every number smaller than it one by one. For example, to check if 29 is prime, you try dividing it by 2, 3, 4, 5, and so on until 28.

The Problem

This manual method is very slow and tiring, especially for big numbers. It wastes time checking many unnecessary numbers and can easily lead to mistakes or missed checks.

The Solution

Using a simple rule, we only check divisors up to the square root of the number. This cuts down the work a lot and quickly tells us if the number is prime or not.

Before vs After

✗ Before

int isPrime(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

✓ After

int isPrime(int number) {
    if (number <= 1) return 0;
    for (int i = 2; i * i <= number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

What It Enables

This method makes it easy and fast to check prime numbers even for very large values.

Real Life Example

Prime numbers are used in computer security to create keys that protect your online information.

Key Takeaways

Manual checking every number is slow and error-prone.

Checking only up to the square root speeds up the process.

This helps in fast prime number detection for many applications.