Checking Prime status of a number

[goelmohit2002]

Hi All,

I read somewhere that the method to use is as below. Can someone please tell what is the reasoning behind checking the divisibility only till square root of number n...as highlighted in point#4 below? Why not check the same till n/2 ?



============================================
1. Pick a number n.
2. Start with the least prime number, 2. See if 2 is a factor
of your number. If it is, your number is not prime.
3. If 2 is not a factor, check to see if the next prime, 3, is a factor. If it
is, your number is not prime.
4. Keep trying the next prime number until you reach one that is a
factor (in which case n is not prime), or you reach a prime
number that is equal to or greater than the square root of n.
5. If you have not found a number less than or equal to the square
root of n, you can be sure that your number is prime.
==============================================

Thanks
Mohit

[sd]

I can understand the theorem and put it to use. But I am curious to know the explanation ....so subscribing to this thread.

[Ben Ku]

Hi Mohit,

I think the easiest way to see this is to use an example. Let's take 36 as an example. The factors of 36 are:

1, 2, 3, 4, 6, 9, 12, 18, and 36.

Because factors come in pairs, we only had to go up to 6 (the square root of 36), because the higher factors pair up with the lower factors.

Let's now consider 91 and apply your algorithm. The square root of 91 is roughly between 9 and 10, so we just need to consider whether it is divisible by all primes up to 9.

2 --> NO
3 --> NO
5 --> NO
7 --> YES

As a result, 91 is NOT prime, because 7 is a factor (and as a consequence, 13 is also a factor).

Hope that helps.