Math & Numbers

Python Program to Check Prime Number

A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself. This example demonstrates an optimized approach checking factors up to √n.

Python Source Code

Editable code sample with line numbers

Python

Expected Output

When this program is compiled and executed, the terminal outputs:

  1 -> is NOT Prime
  2 -> is Prime
 17 -> is Prime
 25 -> is NOT Prime
 29 -> is Prime
 97 -> is Prime
100 -> is NOT Prime

How the Code Works

The function is_prime uses an optimized 6k ± 1 divisibility test. 1. Numbers less than or equal to 1 are immediately ruled out as non-prime. 2. 2 and 3 are handled as prime base cases; all even numbers and multiples of 3 are rejected. 3. All remaining primes greater than 3 can be expressed in the form 6k ± 1. 4. By iterating in steps of 6 up to isqrt(n), we test candidate factors in O(√n) time instead of O(n).

Time Complexity

O(√N)

Space Complexity

O(1)

Key Takeaways & Best Practices

Only check divisors up to √n because any factor larger than √n must pair with one smaller than √n.
Skip even numbers and multiples of 3 to eliminate 66% of candidate divisors.
math.isqrt(n) performs exact integer square root in O(1) space.

Master Python with ZenCompiler

Practice in our high-performance cloud container IDE with multi-file support, interactive terminal STDIN, real-time memory visualizer, and structured lessons.

Related Python Examples

Math & Numbers

O(N)

Python Program for Fibonacci Series

The Fibonacci sequence is a series where each number is the sum of the two preceding ones, starting from 0 and 1. Here we implement iterative generation and generator streaming.