Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
prime number

How do you check if a number is prime in Python?

Educative Answers Team

A prime number is a whole number only divisible by itself and 1. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29.

We can check whether a number is a Prime number by factorizing the number.

svg viewer

Point to remember: The number 1 is neither prime nor composite.

svg viewer

Numbers that have more than two factors are called composite numbers.

Factorization of Non-prime numbers gives us more than two factors. For example 10 is divisible by 1, 2, 5 and 10 itself.

The brute-force approach in this scenario would be to iterate from 2 to p-1. However, it’s helpful to realize the minimum whole number that may divide any number is 2. This means that numbers greater than p/2 do not give a whole number when divided by p.

For example: if p=10p = 10 then p/2=5p/2 = 5;

If 1010 is divided by any number greater than 55, it does not produce whole numbers. Therefore, it is redundant to divide 1010 by numbers greater than 55.

Thus, you can check whether a number p is prime or not by checking whether it is divisible by any number from 2 to p//2.

Note: We use floor division (//) since simple division would give a float answer.

inp = 4

def ran(start, end):
    return range(start, end+1)

if inp > 1:  
   for i in ran(2, inp//2): 
       if (inp % i) == 0: 
           print(inp, "is not a prime number") 
           break
   else: 
       print(inp, "is a prime number") 
  
else: 
   print(inp, "is not a prime number") 

RELATED TAGS

python
prime number
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring