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?

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.

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



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 = 10$ then $p/2 = 5$;

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

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