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 then ;
If is divided by any number greater than , it does not produce whole numbers. Therefore, it is redundant to divide by numbers greater than .
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 = 4def 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")breakelse:print(inp, "is a prime number")else:print(inp, "is not a prime number")
Free Resources
