Why Check if Number is Prime in DSA Python?

The Big Idea

Discover the simple trick that makes checking primes lightning fast!

The Scenario

Imagine you want to find out if a number is prime by trying to divide it by every number smaller than itself. For example, to check if 29 is prime, you try dividing it by 2, 3, 4, 5, and so on, all the way up to 28.

The Problem

This manual method is very slow and tiring, especially for big numbers. It takes a lot of time and you might make mistakes by missing some divisors or doing unnecessary checks.

The Solution

Using a simple rule, you only need to check divisors up to the square root of the number. This makes the process much faster and easier to do without errors.

Before vs After

✗ Before

def is_prime(number):
    if number <= 1:
        return False
    for i in range(2, number):
        if number % i == 0:
            return False
    return True

✓ After

def is_prime(number):
    if number <= 1:
        return False
    for i in range(2, int(number ** 0.5) + 1):
        if number % i == 0:
            return False
    return True

What It Enables

This method lets you quickly and correctly find out if numbers are prime, even when they are very large.

Real Life Example

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

Key Takeaways

Checking all numbers up to the number itself is slow and inefficient.

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

This simple trick helps in many real-world applications like encryption.