Prime or composite is the question:

Question

(1) 191
(2) 337
(3) 527
(4) 649
(5) 919
(6) 961

To a certain extent this is about divisibility rules, but finding a fast an efficient way to determine if relatively small numbers are prime is what this is really about. I promise you that method does exist for these problems. BTW, there is no known fast an efficient way to do this for any given integer, so the problem isn't trivial. It will definitely deepen your understanding of number properties.

(1), (2), and (5) are primes

fluke · Answer

Are you talking about this:

If a number is NOT divisible by any prime number between 2 and square root of the number itself, inclusive, the number will be prime.

So,  x  will be prime if it is NOT divisible by any prime number between 2 and  \sqrt{x} , inclusive.

BenchPrepGURU · Answer

Exactly. My students seem to struggle with this idea, so I thought I would put up a question about it. It seems that an explanation is not really needed.

144144 · Answer

Hey BenchPrepGURU, +1 for the question.
But I still would like to see the explanation. How do you extract a quick root of 961 for example?
Solving this question will take me more than 2 min. I would be happy if we can discuss it a bit more. Thanks.

GyanOne · Answer

144144,

BenchPrepGURU used an example to illustrate a useful method to find whether a number is prime or not.

If you need to find the square root of 961, then here is a quick estimation method:

First find the range that the square root of 961 could lie in. You know that the square of 30 is 900 and the square of 40 is 1600, so the square root of 961 should lie between 30 and 40. Since 961 is much closer to 900 than it is to 1600, the square root will be much closer to 30 than 40. Lets try 31 first. 31^2 = 961, and we have found our answer.

If you need to find the exact square root down to a few decimals, then the best way is to use the division method. For details of this, please see the section 'Decimal (base 10)' in the Wikipedia article on 'Methods of computing square roots' for a quick tutorial and a couple of examples.

144144 · Answer

wow, GyanOne.

Great answer.

Thanks. +1

BenchPrepGURU · Answer

I guess a complete explanation is in order:

When trying to determine whether a large number (by 'large' I mean something not within your typical mental math spectrum - the 12 x 12 multiplication table, squares for integers less than or equal to 25, and powers of primes) checking for divisors can become tedious unless you really understand what you're doing.

1. You should only check for prime divisors - if something's not divisible by 2, then it won't be divisible by any multiple of 2, so even though we have good divisibility rules for 4, 6, 8, and 10 we shouldn't check these rules. Check for divisibility for 2, 3, 5, 7, 11, 13, 17, 19, 23, etc. It's true that many of these don't have good divisibility rules, but at least we're not doing any redundant work.

2. You only need to check primes less than the square root of the number you're investigating. This is because factors come in pairs, one of them will always be less than or equal than the root of the product... so if you're going to find a factor of x you find it between 2 and  \sqrt{x}

Example:
197. It's easy to see that  14<\sqrt{197}<15 . (Well, maybe it's not 'easy' but it should be - if you're serious about sending the GMAT home crying to its momma, you should know all your squares up to 25 as well as powers of primes up to  2^10, 3^5, 5^4, 7^3, 11^3 ) Anyway, this means we need to check all the primes less than 14. 2 - NO, 3 - NO, 5 - NO, 7 - NO, 11 - NO. I checked 7 in my head, and the rest I checked using divisibility rules. If you don't know the rule for 11, you should learn it. Because 197 has no prime factors less than 14, it must be prime.

Try 337, 527, 649, 919 on your own.

Prime or composite is the question:

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards