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

[zenithexe]

try to go through the rule by using already known prime numbers

eg if n=17,

17/2=not divisible
17/3=not divisible
17/5=not divisible
17/7=not divisible
17/11=not divisible
17/11=not divisible

can you tell that steps after 17/3 are redundant?
as you know sqrt(17) is just little over 4 (as sqrt(16)=4)

Steps after sqrt(n) are redundant because;

n can written this way

n=x*y
as x increases, y must decrease to maintain n,
for example

if n=16
n=16*1, 8*2, 4*4, 2*8, 1*16
as you can see, 16*1 and 1*8 repeats
so steps after 4*4 (ie, sqrt(n)) are not necessary


hmm, I hope this makes sense

[goelmohit2002]

try to go through the rule by using already known prime numbers

eg if n=17,

17/2=not divisible
17/3=not divisible
17/5=not divisible
17/7=not divisible
17/11=not divisible
17/11=not divisible

can you tell that steps after 17/3 are redundant?
as you know sqrt(17) is just little over 4 (as sqrt(16)=4)

Steps after sqrt(n) are redundant because;

n can written this way

n=x*y
as x increases, y must decrease to maintain n,
for example

if n=16
n=16*1, 8*2, 4*4, 2*8, 1*16
as you can see, 16*1 and 1*8 repeats
so steps after 4*4 (ie, sqrt(n)) are not necessary


hmm, I hope this makes sense

Thanks.....but can you please tell for what reason we should not check the divisibility by 5, 7 ?

They too are prime numbers....and greater then 4....

what is the reason why we stop after checking till 4 ?

[quant-master]

Hi,

I guess you posted this in Test-Magic forum as well, not sure though. Well here is my explanation. (Its same as what I posted there )

Anyways here we go,

To understand this you need to understand the concepts of factor.
Every number is made up of factors and for each factor there is factor-pair. For example lets take the number 18

18 is made of one two and two 3s.

factors of 18 can be expressed as below

1-----18
2------9
3------6

In the above representation (1,18),(2,9) and (3,6) are factor-pairs. When you multiply the factor pairs it will lead to the original number itself, in this case it's 18.

Generally for a number N, N2 will have k factors less than N and k factors more than N. Now lets come to the root of your question. Let N2 be a square of a number say N. Than there will be k factors less than N and k factors more than N.

For example let's take the square of a a number 6 which is 36. Now its factors are 1,2,3,4,6,9,12,18,36. Now if you notice there are 4 factors less than 6 and 4 factors more than 6 and for every factor less than 6 there is a factor pair which is more than 6.

Now if you take a prime number P there must be k factors less than square root of P and k factors more than square root of P. Since prime number will have only 1 and P as its factors there is no factor apart from 1 which is less than square root of P, this means that there can't be any factor more than square root of P as this will violate factor-pair concept. Hence you need not check for the prime numbers which is more than square root of P

Hope I am clear.

This was supposed to be my next concept thread in my blog

Thanks,
Quant-Master