Checking Prime status of a number

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

zenithexe wrote: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 ?

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