primality check

SHORT CUT PROCESS TO CHECK WHETHER A NUMBER IS PRIME OR NOT

Follow the below steps:
a) Take the square root of a number.
b) Round of the square root to the immediately lower integer. Call this 'z'. For example if you have to check for 181, its square root will be 13.xx. Hence, the value of z, in this case will be 13.
c) Check for the divisibility of the number N by all prime numbers below z. If there is no prime number below the value of z which divides N then the number N will be prime.


TO ILLUSTRATE:

The value of √239 lies between 15 (15^2=225) and (16^2=256). Hence, take the value of z as 15.

Prime numbers less than 15 are 2,3,5,7,11 and 13. 239 is not divisible by any of these. Hence you can conclude that 239 is a prime number.

A BRIEF LOOK INTO WHY THIS WORKS?
--->Suppose you are asked to find the factors of the number 40.
An untrained mind will find the factors as : 1,2,4,5,8,10,20 and 40.
An untrained mind will find the factors as :
1 X 40
2 X 20
4 X 10
5 X 8
The discovery of one factor will automatically yield another factor. In other words, factors will appear in terms of what can be called as FACTOR PAIRS.
Now take a look again at the pairs in the example above. If you compare the values in each pair with the √40 (i.e. 6.xx) you will find that for each pair the number in the left column is lower than the square root of 40, while the number in the right column is higher than the square root of 40.
This is a property for all numbers and is always true.

WHENEVER YOU HAVE TO FIND THE FACTORS OF ANY NUMBER N, YOU WILL GET THE FACTORS IN PAIRS (I.E. FACTOR PAIRS). FURTHER THE FACTOR PAIRS WILL BE SUCH THAT IN EACH PAIR OF FACTORS, ONE OF THE FACTORS WILL BE LOWER THAN THE SQUARE ROOT OF N WHILE THE OTHER WILL BE HIGHER THAN THE SQUARE ROOT OF N. IF WE ARE NOT ABLE TO FIND A FACTOR OF A NUMBER UPTO THE VALUE OF ITS SQUARE ROOT, WE WILL NOT BE ABLE TO FIND ANY FACTOR ABOVE THE SQUARE ROOT AND THE NUMBER UNDER CONSIDERATION WILL BE A PRIME NUMBER.

This is the reason why when we need to check whether a number is prime, we have to check for factors only below the square root.


WHY DO WE HAVE TO CHECK FOR THE DIVISIBILITY ONLY WITH PRIME NUMBERS?

Take for example, in order to find whether 181 is a prime number, we need to check with the numbers = 2,3,4,5,6,7,8,9,10,11,12 and 13.

a)The first thing you will realize, when you first look at the list above is that all even numbers get eliminated automatically. (since no even number can divide an odd number and of course you will check a number for being prime only if it's odd).
This will leave you to numbers 3,5,7,9,11 and 13 to check 181.
b)You do not need to check with composite numbers below the square root. How?

From the above list, the only composite number is 9. So why we do not check for the divisibility of the number 9?
Case 1) IF N IS DIVISIBLE BY 3 When you check N for divisibility by 3, N will automatically become non-prime. Hence you will need not check the divisibility of 9.
Case 2) IF N IS NOT DIVISIBLE BY 3 If N is not divisible by 3, it is obvious that it is not divisible by 9.

Thus, in either case, checking for the divisibility of a composite number will become useless.

HENCE, WHEN WE HAVE TO CHECK WHETHER A NUMBER IN IS PRIME OR NOT, WE NEED TO ONLY CHECK FOR ITS DIVISIBILITY BY PRIME FACTORS BELOW THE SQUARE ROOT OF N

Also, one would never really need to check with the prime number 5, because divisibility by 5 would automatically be visible and thus, there is no danger of anyone even declaring a number like 35 a prime number. Hence, in the list of prime numbers below the square root we would never include 5 as a prime number to check with.

CHECK WHETHER A NUMBER IS PRIME (FOR NUMBERS BELOW 49)
The only number you would need to check for divisibility with is number 3. Thus, 47 is a prime because it is not divisible by 3.

CHECK WHETHER A NUMBER IS PRIME (FOR NUMBERS ABOVE 49 AND BELOW 121)
Naturally you would need to check this with 3 and 7. But if you remember that 77,91 and 119 are not prime, you would be able to spot the prime numbers below 121 by just checking for divisibility with the number 3.
Why?
Well, the odd numbers between 49 and 121 which are divisible by 7 are 63,77,91,105 and 119. Out of these perhaps 91 ans 119 are the only numbers you can mistakenly declare as a prime. 77 and 105 are so obviously not-prime that you would never be in danger of declaring them prime.

Thus, for numbers between 49 and 121 you can find whether a number is prime or not by just dividing by 3 and checking for its divisibility.

CHECK WHETHER A NUMBER IS PRIME (FOR NUMBERS ABOVE 121 AND BELOW 169)
Naturally you would need to check this with 3, 7 and 11. But if you remember that 133,143 and 161 are not prime, you would be able to spot the prime numbers between 121 and 169 by just checking for divisibility with the number 3.
Why?
Well, the odd numbers between 121 and 169 which are divisible by 7 or 11 are 133,143,147,161 and 165. Out of these perhaps 133,143 and 161 are the only numbers you can mistakenly declare as a prime if you do not check for 7 or 11. The number 147 would be found to be not prime when you check its divisibility by 3 while the number 165 you would never need to check, for obvious reasons.

Thus, for numbers between 121 and 169 you can find whether a number is prime or not by just dividing by 3 and checking for its divisibility.

Thus, we have been able to go all the way till 169 with just checking the divisibility with the number 3.


Hope this helps!

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.