BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

Checking Prime status of a number

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Legendary Member
Posts: 1799
Joined: Wed Dec 24, 2008 3:03 am
Thanked: 36 times
Followed by:2 members

Checking Prime status of a number

by goelmohit2002 » Sun Aug 02, 2009 12:43 pm
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
Top
Source: — Problem Solving |
Senior | Next Rank: 100 Posts
Posts: 49
Joined: Tue Jun 16, 2009 8:20 pm
Thanked: 5 times

by zenithexe » Sun Aug 02, 2009 6:30 pm
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
Top
Legendary Member
Posts: 1799
Joined: Wed Dec 24, 2008 3:03 am
Thanked: 36 times
Followed by:2 members

by goelmohit2002 » Mon Aug 03, 2009 10:16 am
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 ?
Top
Senior | Next Rank: 100 Posts
Posts: 74
Joined: Fri Jul 31, 2009 11:38 am
Thanked: 4 times
Followed by:1 members

by quant-master » Mon Aug 03, 2009 11:02 am
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 :P )

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 :D

Thanks,
Quant-Master
https://gmat-quants.blocked - My Blog Updated almost daily with new quant fundas. Find collection of quants question in my blog
Top
Post new topic Post Reply
• Page 1 of 1