PyRun
Py 3.11

Python Prime Checker Algorithm

Check if a number is prime using Python. Run our interactive algorithm to see efficient mathematical iteration and root evaluation.

Try Python Prime Checker Algorithm Code

How it Works

A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself.

The most inefficient way to check for a prime is iterating up to the number itself. A powerful optimization is to only check divisibility up to the square root of the number.

Source Code

Efficient prime checking algorithm demonstrating the O(sqrt(n)) optimization.

prime_checker.py
Try in Editor
import math

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
        
    max_divisor = math.isqrt(n)
    for i in range(3, max_divisor + 1, 2):
        if n % i == 0:
            return False
            
    return True

test_numbers = [2, 10, 17, 25, 97]
for num in test_numbers:
    status = "Prime" if is_prime(num) else "Not Prime"
    print(f"{num:2d} -> {status}")
Terminal Output
 2 -> Prime
10 -> Not Prime
17 -> Prime
25 -> Not Prime
97 -> Prime

Real-world Applications

  • Cryptography and hashing algorithms
  • Educational mathematics and sieve theory
  • Backend validation for secure keys

Frequently Asked Questions

Why check only up to the square root?

If $n = a \times b$, then at least one of the factors ($a$ or $b$) must be less than or equal to the square root of $n$. Thus, checking higher is redundant.

More Examples

Python Fibonacci Sequence Generator
Run and understand the Fibonacci sequence in Python. This interactive code example shows iterative and recursive approaches to generating Fibonacci numbers.
Python Sorting Algorithms
Explore python sorting algorithms. Visualize bubble sort and merge sort natively within a browser IDE context.