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
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
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
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")
View all Courses