How many prime numbers exist between 260 and 280?

Solution:

\(260=2*5!+20\), \(280=2*5!+40\).

Find out Prime Numbers between 20 and 40.-->23,29,31, and 37--> total 4.

Ans.E.

Hi AdlaT,

Can you please brief me about your approach..??
Why did you break into \(260=2*5!+20\), \(280=2*5!+40\).
and then looking for prime between 20 and 40...??

Please explain

For Example. take 2*5!+21, which is 261, we can factor out 3--->2*2*3*4*5+7*3=3( 2*2*4*5+7)

2*5!+22 ,which is 262, we can factor out 2 ---->2*2*3*4*5+11*2=2(2*3*4*5+11)

2*5!+23, which is 263, we can not factor out any integer(>1) from this number thus 263 is a prime number.

same for other numbers .

hope this helps.

Straight a way lets exclude all the Even numbers between 260 and 280.
So now the number starts from 261 to 279 (Only ODD)
261 is a divisible of 3 and next odd divisible by 3 will be 261 + 6 = 267 + 6 = 273 + 6 =279.
Also we can eliminate numbers ending with '5'
So in Odd, the excluded numbers are 261,265,267,273,279, which leave us with 263,269,271,277.
Checked the above listed four numbers are divisible by any numbers till 20.
Choosing E.

What you can use is the fact that all prime numbers >3 will be of the form 6n + 1 or 6n-1. What is the first multiple of 6 between 260 and 280?

It is 264 --> check for 263 and 265 (263 is a prime number).

Next multiple of 6 = 270 ---> check for 269 and 271 (both are primes)

Finally, next multiple of 6 ---> 276 ----> check for 275 and 277 (clearly 277 is a prime).

Thus you get 4 prime numbers between 260 and 280.

Hope this helps.

You dont have to go to more than 17 for checking as 17^2 =289

Hi AdlaT,

Sorry to say but I didn't got your approach.
Actually, I have seen an approach in which big numbers are given eg- 737 to 943 (Just a random range)
And then we break these no into something...In the end we get an range which is below 100 and we just need to calculate the prime no between them..

Nut unfortunately I am not able to recall that approach.

Your approach seems to be quiet similar
As you just calculate the prime no.s between 20 and 40

How did you reached to this thing.

Total No of prime numbers between 20 to 40 = Total No of prime numbers between 260 to 280

Can you please assist..?

I will try to explain my strategy.

260 and 280 can be expressed as product of smallest possible integers plus smallest possible integer.

because i know exactly what are the prime numbers less than 100, which makes problem easy for me.

260 can be expressed in smallest possible integers as 2*2*3*4*5+20

and 280 can be expressed as in smallest possible integers as 2*2*3*4*5+40.

now you can see the base value which is 2*2*3*4*5 is common in both values, now you can find the prime numbers easily from 20 to 40.

Your Question.

How many prime numbers exist between 737 and 943?


Solution:

737 Can be expressed as 6!+17.
943 can be expressed as 6!+ 223. base should be the same in minimum and maximum numbers.

in this case i need to know prime numbers greater than 100, which is time consuming. i will break this range in to range of 100.

so 6!+17(=737) to 6!+100(820)--> prime numbers between 17 and 100 are 19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97=18.
But you should also consider 6!+49, 6!+77 and 6!+91-->Total 18+3=21 prime numbers between 737 and 820.

now Between 820 and 840.

7*5!-0+to 7*5!-20 , you can not factor out 11,13,17, and 19--4 prime numers,

Now between 840 and 943


7*5!+0 to 7*5!+101 ---total prime numbers between 0 and 103 are 26.

Total prime numbers between between 737 and 943=21+4+26=51.

hope it helps.

Hi AdlaT,

Thank you so much for such a detailed explanation. Although I didn't got 100% but got a little.
You really deserve kudos for trying soo hard to make me understand...
Thanks :D

Not sure I understand AdlaT's method. To help me wrap my mind around it, I considered a simplified version of it:

\(x = n! + k\)
If there exists an a common factor \(a\geq2\) of both \(n!\) and \(k\) , then \(x\) is not prime. In fact if \(k\) itself is prime then \(x\) should be prime as well, according to the method.


I tried to find the prime numbers between 220 and 226. (This is a different range from the OP, but it helps me better understand this method.)
I chose \(n=5\), such that \(n! = 5! = 120 = 2^3*3*5\)
Then I tested all odd numbers 225, 223 and 219 as prime candidates with the method above.


case #1: \(225 = 5! + 105 = 2^3*3*5 + 3*5*7\)
There is a common factor \(a\geq2\) in that \(a=3*5=15\); 105 is also not prime. 225 is thus not prime. I got that.


case #2: \(223 = 5! + 103 = 2^3*3*5 + 103\)
There is no common factor \(a\geq2\); 103 is also prime. 223 should thus be prime. It is indeed prime.


case #3: \(221 = 5! + 101 = 2^3*3*5 + 101\)
There is no common factor \(a\geq2\); 101 is also prime. 221 should thus be prime. But it’s not: \(221 = 13*17\) ???


Given these cases, I believe I do not understand the simplified version of AdlaT's method.

In order to exclude non-primes, I had to test the prime candidates again. Some other possible common factors are the prime numbers in the following range: \(largest\_prime\_factor\_of\_n! < factors\_to\_test \leq \sqrt{upper\_range\_value}\), i.e. \(5 < factors\_to\_test <= 15\) in the example above. These possible factors are the primes 7, 11 and 13.
So I tested my collection of possible primes {223, 221} as to whether any of {7, 11, 13} may be a factor. 221 (=13*17) was thus excluded as non-prime. The only prime was 223.

Because I can now find prime faster than before, AdlaT earns my kudos.

prime numbers can end 1,3,7,9

we have 261, 263, 267, 269, 271, 273, 277, 279

all removed are divisible by 3, so only four numbers remain

E

Hi ENGRTOMBA2018
But how can you be sure 263, 269, 271,... are prime, you still need to estimate if it divisible by 7,11,13, etc?

Not really as all primes >3 would be of the form 6k+1 or 6k-1. If the multiples of 6 between 260 and 280 are 264, 270, 276 etc 264-1 would be prime etc. Thus, 263 would be prime. Similarly, 270+1 would be prime as well.

Hope this helps.

I listed manually numbers from 260 to 280, excluding even ones and the ones end with 5, so i got
261, div by 3
263, prime
267, div by 3
269, prime
271, prime
273, div by 3
277, prime
279, div by 3.
We are left with 263, 269, 271, and 277. Answer is E

We know that any even number greater than 2 is not prime, and any number greater than 5 that ends in 5 or 0 is not prime. Let’s now list the odd multiples of 3 between 260 and 280 (recall that a number is a multiple of 3 if the sum of its digits is a multiple of 3):

261, 267, 273, and 279

These numbers will not be prime since they are multiples of 3. Now let’s see the numbers we are left with(after the multiples of 2, 3 and/or 5 are excluded):

263, 269, 271, 277

All of the above numbers are prime.

Answer: E

Divisibility rules of 2 , 3 and 5 play a huge role when i did this question.

Time taken 1:22.

There are only 4 number prime - 271 , 269 , 271 , 277.

It's sometimes unfortunate that this site uses kudos to determine which posts rise to the top of a thread, because sometimes solutions that are incorrect end up featured, and can mislead readers. That's the case here.

It's true that prime numbers will be of the form 6n-1 or 6n+1, at least once you get beyond the smallest primes. But there's no *guarantee* that a number of the form 6n+1 or 6n-1 is prime. If the range in this question were different -- say it asked how many prime numbers there are between 240 and 260 -- then you'd think, just by finding numbers in the form 6n-1 and 6n+1, that 253 was prime (because it equals 6*42 + 1, so is in the form 6n+1). But it is not prime: 253 = 23*11. It's really just a lucky coincidence that the numbers from 260 to 280 that look like 6n-1 or 6n+1 are all prime in this question, once we rule out multiples of 5.

Unfortunately, very few of the solutions posted above are mathematically correct (the only correct solutions are the ones from sowragu and from nalinair, though neither fully explains the method they're using). We can easily rule out numbers between 260 and 280 that are not prime -- the even numbers are not, the numbers ending in '5' are not, and the numbers whose digits sum to a multiple of 3 are not. That leaves us with these candidates:

263, 269, 271, 277

But all we've proven so far is that the four numbers above are not divisible by 2, 3 or 5. We haven't come close to proving they're prime -- how do we know they aren't divisible by 7, say, or by 13? We have to check that. The most efficient way to prove a large number x is prime is to prove that it cannot be divided by any primes up to √x. If you can't divide x by any primes less than or equal to √x, then x is a prime number. So here, since √277 is just less than 17, to prove the numbers above are prime, we need to check if we can divide them by any prime less than 17. We've checked for 2, 3 and 5, but we still need to check for 7, 11 and 13. I'd do that by locating the easy multiples of 7, 11 and 13 that are nearby:

280 is a multiple of 7, so these are as well (subtracting 7s) : 273, 266, 259 --> none of our four candidates is a multiple of 7
220 is a multiple of 11, so these are as well (adding 44, 55 and 66): 264, 275, 286 --> none of our four candidates is a multiple of 11
260 is a multiple of 13, so these are as well (adding 13s): 273, 286 --> none of our four candidates is a multiple of 13

With all of that work done, we can safely conclude that the four candidates are all indeed prime numbers, so the answer is four.

Incidentally, to reliably test whether numbers this size are prime is a very time-consuming process, which is why no real GMAT question ever asks you to do it.