Trusted answers to developer questions

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.

Point to remember: The number

1is 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

Copyright ยฉ2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses