Start learning free

LESSON 135 OF 410 · LOOPS & CONDITIONALS

Prime Number in O(n) Time Complexity using Python

Practice Read the full explanation

Given a non-negative integer n check if it is a prime number

Prime numbers are positive numbers greater than 1 that are divisible only by 1 and the number itself.

Examples of prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23

Example 1:

Input: n = 31
Output: True

Example 2:

Input: n = 6
Output: False
Explanation: 6 is divisible by 2 and 3.

Note:

Your algorithm should run in O(n) time and use O(1) space.

Hints:

Prime numbers are only divisible by the number 1 or itself. Let's reformulate this definition a little bit:
A number n is prime if and only if there is no such number d such that 1 < d < n and d is a divisor of n. Is this new definition more helpful?

We should iterate through each number d from 2 to n - 1 and check if d is a divisor of n.
If we find such a number, we can conclude that n is not prime and return False right away:

for each d : 2 -> n - 1:
	if d is divisor of n:
		return False

How do we check if d is divisor of n? When should we return True?

d is divisor of n (or n is a multiple of d) if and only if n % d == 0:

for each d : 2 -> n - 1:
	if n % d == 0:
		return False
return True

As you can see, if the for loop terminates and we reach the return True line of code, we know that we haven't found a divisor, so it's safe to say n is prime.

We have a for loop that performs exactly n - 2 iterations, thus the Time Complexity is O(n).
The only extra space we use is the iterator variable d inside the loop, thus the Extra Space used is O(1).

STEP 1 OF 4

Guided

Ctrl + Enter to check

PYTHON · LOOPS & CONDITIONALS

Prime Number in Python, explained

Problem Definition

We need to determine if a given non-negative integer n is a prime number. A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself.

Input

A non-negative integer n.

Output

A boolean value: true if n is a prime number, false otherwise.

Constraints

n is a non-negative integer.

Example

Input: n = 31
Output: true

Input: n = 6
Output: false
Explanation: 6 is divisible by 2 and 3.

Understanding the Problem

The core challenge is to efficiently determine if a number is prime. Prime numbers have significant applications in cryptography, number theory, and computer science. A common pitfall is to assume that checking divisibility up to n-1 is necessary, which is not optimal.

Approach

To solve this problem, we can start with a naive approach and then optimize it.

Naive Solution

We can iterate through each number d from 2 to n-1 and check if d is a divisor of n. If we find such a number, n is not prime.

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

This approach has a time complexity of O(n), which is not efficient for large values of n.

Optimized Solution

We can improve the efficiency by iterating only up to the square root of n. If n is divisible by any number greater than its square root, it must also be divisible by a number smaller than its square root.

import math

def is_prime(n):
    if n <= 1:
        return False
    for d in range(2, int(math.sqrt(n)) + 1):
        if n % d == 0:
            return False
    return True

This approach reduces the time complexity to O(√n), which is much more efficient.

Algorithm

Let's break down the optimized algorithm step-by-step:

Check if n is less than or equal to 1. If so, return false.
Iterate from 2 to the square root of n.
For each number d, check if n is divisible by d. If so, return false.
If no divisors are found, return true.

Code Implementation

Here is the Python code for the optimized solution:

import math

def is_prime(n):
    # Check if n is less than or equal to 1
    if n <= 1:
        return False
    # Iterate from 2 to the square root of n
    for d in range(2, int(math.sqrt(n)) + 1):
        # Check if n is divisible by d
        if n % d == 0:
            return False
    # If no divisors are found, n is prime
    return True

Complexity Analysis

The time complexity of the optimized solution is O(√n) because we only iterate up to the square root of n. The space complexity is O(1) as we are not using any additional space.

Edge Cases

Consider the following edge cases:

n = 0: Should return false.
n = 1: Should return false.
n = 2: Should return true (2 is the smallest prime number).

Testing

To test the solution comprehensively, consider a variety of test cases:

def test_is_prime():
    assert is_prime(0) == False
    assert is_prime(1) == False
    assert is_prime(2) == True
    assert is_prime(3) == True
    assert is_prime(4) == False
    assert is_prime(17) == True
    assert is_prime(18) == False
    assert is_prime(19) == True
    assert is_prime(20) == False
    assert is_prime(31) == True
    print("All tests passed.")

test_is_prime()

Thinking and Problem-Solving Tips

When approaching such problems:

Understand the definition and properties of the concept (e.g., prime numbers).
Start with a simple, naive solution and then look for optimizations.
Consider mathematical properties that can reduce the number of operations.
Practice solving similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to determine if a number is prime. We started with a naive approach and then optimized it to achieve better performance. Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science.

Additional Resources

For further reading and practice problems, consider the following resources:

Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free