isprime Python Function Efficient Logic

isprime Python Function Efficient Logic – This Python programming tutorial will explain:

Definition of a Prime Number with examples
Is 1 prime or Composite?
Defining a Composite number with examples
How to Write isprime python function?
Explanatin of the Logic of isprime Python function
The source code and output of the python program

isprime Python Function Returns True False

What is a Prime Number?

Proper Definition of a Prime Number:
A prime number is a positive whole number (greater than 1) that is divisible only by itself and 1. It means that a Prime Number has only TWO divisors.

For example 2, 3, 5, 7, 11 are prime numbers, because they all have only two divisors, 1 and the number itself.

What is a Composite Number?

A composite number is a positive whole number (greater than 1) that has more than two divisors.

For example:
4 is composite, since it has three divisors: 1, 2 and 4

Examples and Reason of Some Prime and Composite Numbers:

Why 1 is neither a prime nor a composite.

The number 1 is not a prime, because it has only one divisor, whereas a prime number has exactly two divisors. that is 1. Moreover 1 is not composite because it has only one divisor and a composite has more than two divisors.

2 is prime because it has only two divisors, that is 1 and 2.
4 is composite because it has more than two divisors that is 1, 2 and 4.

2 is the only Even prime number

What is a Prime Number?
Proper Definition of a Prime Number
A prime number is a positive whole number (greater than 1) that is divisible only by itself and 1. It means that a Prime Number has only TWO divisors.

For example 2, 3, 5, 7, 11 are prime numbers, because they all have only two divisors, 1 and itself.

The Programming Logic behind isprime Python Function Efficient Logic

Now we know that a prime number has only two divisors 1 and itself. Therefore, we find another divisor of the number, if we find it, then the number is not prime.

The Simple old Logic of isprime python function

For this purpose, one older simple logic was to divide the given number from 2 to n/2 (half of number). That is if number is 37 then we will divide it with 2 to 18.

Note: We will use integer division and ignore fractional part. So, we will consider 37/2 as 18 and not 18.5.

Therefore, the loop will execute from 2 to 18 for 17 times. This is an inefficient logic.

The Efficient Logic for isprime Python Function Efficient Logic: Using sqrt function for maximum possible divisor

The efficient logic is to use sqrt(number) as maximum possible divisor. For example, if the number is 37, the sqrt function will return square root of 37 as 6.082762530298219, but we will ignore fractional part by converting float to int. Hence, the loop will execute for 2 to 6.

Therefore the loop will execute now for only 5 times from 2 to 6. This will improve the program efficiency, as it may take a olot of less time to execute for the larger numbers.

Why we use sqrt function in isprime?

Since using sqrt function will reduce the number of time the main divisor checking loop is executed in isprime.

With above mentioned nubers and proof we conclude that:

Using sqrt function, the loop will execute only for 5 times to check a number 37 for prime number. But the simple 2 to n/2 logic will repeat the loop body for 17 times.

The reason behind this is the fact:

“A non-prime-number’s maximum possible factor / divisor is lthe square root of that number, because:

sqrroot(n) * sqrroot(n) = n.

Example: let n=100 then

sqrroot(n) * sqrroot(n) = n. will be 10 x 10 =100, therefore we will find a factor / divisor of 100 from 2 to 10 (square root).

Example: Let the number is n=101, the square root of 101 is about 10.049875621. Thus, 10.049875621 x 10.049875621=101. Therefore, we have to check for divisor between 2 to 10.

Another Explanation for sqrt use in isprime:

Because if a and b are two factors / divisors of a number n=100. Then squareroot(100) is 10 so that 10 x 10 =100.
Now if one factor is larger than the square root 10, the other factor must be smaller than the square root 10.
For example, if bigger divisor is 20 then the smaller will be 5. So that 5 x 20 =100. It proves that if a number is not prime then it will have a divisor smaller than square root. Hence we use a loop from 2 to squareroot(n).

The Source code of isprime Python Function

# Write a Python function is_prime(num)
# that takes a number and checks it for prime
# number. It returns true or false.
# Use this function in the program.
# Author: www.EasyCodeBook.com (c)
from math import sqrt
def is_prime(num):
    """ This function returns true if given number is prime """
    if num<2:
        return False
    max_divisor = sqrt(num)
    max_divisor = int(max_divisor)
    
    for i in range(2,max_divisor+1):
        if num % i == 0:
            return False

    return True    


n= int(input('Enter a numbet to check for Prime:'))

# call the function with actual
# parameter n
result = is_prime(n)

if result:
    print(n,'is a Prime Number')
else:
    print(n,'is not a Prime Number')

The output of a sample run of the Python program is:
Enter a numbet to check for Prime:1500
1500 is not a Prime Number

Another output:

Enter a numbet to check for Prime:37
37 is a Prime Number