How to Determine the Prime Number in Python

In this example, we will learn how to determine the prime number in Python.

Source Code

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

# Enter a number and cast to integer
num = int(input("Please enter a number: "))

# Prime number must be greater than 1
if num > 1:
    # Set for loop from 2 to num-1 and check whether there is a factor, if found, then it is not prime number.
    for i in range(2, num):
        if (num % i) == 0:
            print(num, " is not prime number")
            print(i, "*", num // i, "is", num)
        print(num, "is prime number")

    print(num, "is not prime number")
Please enter a number: 8
8  is not prime number
2 * 4 is 8

Please enter a number: 5
5 is prime number

4. Think More

The method above is in low efficiency.  We know that if a number can be factorized, then the two numbers a and b obtained during the decomposition must have this situation: a is less than or equal to sqrt(n) and b is greater than or equal to sqrt(n). Based on this, the codes above can be optimized. We just need traverse to sqrt(n) and stop there.  This is because if no divisor is found on the left side of sqrt(n), we can not find it on the right side as well.

Notify of
Inline Feedbacks
View all comments