Top

How to Find Prime Numbers

Prime numbers are the category of natural numbers which are greater than 1 and are divisible only by 1 and itself. Prime numbers do not give zero as remainder when divided by any other number than 1 or itself. The property of a number being prime is known as primality and the method of testing a number whether it is prime, is called primality test.

According to Primality test, following steps should be followed while testing a number for being prime (let us consider a natural number x which is to be tested):

• Divide x by 2. If the quotient is integer which means x is divisible by 2, then it is concluded that the number is not prime, else follow next step.
• Divide x by 3. If the quotient is integer which implies that 3 is a divisor of x. In such case it is concluded that the given number is not prime, otherwise follow next step.
• Continue dividing by successive numbers and check for the remainder.
• Stop the process of division till dividing by $\sqrt{x}$, because after $\sqrt{x}$, the factors start repeating themselves.
• If from 2 to $\sqrt{x}$, the number x is not divisible by any number, then it means that x is prime, otherwise not prime.

No need to check by numbers like 2, 6, 9, 10, 12 etc, if already checked for their prime factors 2, 3 and 5 etc.Let us take an example to understand this method clearly.

Example: Check whether 91 is prime.
Solution:
Step 1 -
On dividing 91 by 2, we get 45.5 (quotient is not integer). Therefore, 91 is not divisible by 2.
Step 2 - On dividing 91 by 3, we get 30.3333. Therefore, 91 is not divisible by 3.
Step 3 - Since 91 is not divisible by 2 and 2 is a prime factor of 4. Therefore, 91 is not divisible by 4 also.
Step 4 -
On dividing 91 by 5, we get 18.2. Therefore, 91 is not divisible by 5.
Step 5 - Since 91 is not divisible by 3 and 3 is a prime factor of 6. Therefore, 91 is not divisible by 6 also.
Step 6 - On dividing 91 by 7, we get 13. Therefore, 91 is divisible by 7. Therefore, 91 is divisible by a number other than 0 or itself.
Hence, 91 is not a prime number.

 Related Calculators Find Prime Factorization Calculator Calculate Prime Number Find Factors of a Number Calculator Calculate Prime Factors

*AP and SAT are registered trademarks of the College Board.