## The Third Cellar

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

After travelling through the secret passage, also know as the "Communists' Road", they entered the third cellar. This is rumoured to be the entrance to the Phantom's house on the lake. In the third cellar are a bunch of trompe-l'œil, used for the background scenes by the opera house (back then they only have paintings to make a 3D looking background). You find 6 trompe-l'œil on each side. Each one has one and only one decimal digit. The numbers on each side assembles to a 6 digit number. The Persian explains: the Phantom really likes primes. The two numbers here represents a left-closed, right-open bounded interval, and the number of primes in this interval determines how many stones you must drop into the hole beside a boulder. One stone will be dropped every second, and the boulder will only move out of the way after you stopped at the right number for a second. Otherwise, the boulder will roll over all of you. Since Christine's life is in more danger now, you get the same amount of time as before, 1 second, to solve this problem.

But really, the Phantom knows that you just wrote your program the easiest way possible, and doesn't scale up for the challenge. Poor you have to rewrite your program more efficiently.

#### Input Specification

The first line is the number , always smaller than 20, the number of test cases to follow. The next lines are two natural numbers, as written on the trompe-l'œil, which are guaranteed to be smaller than .

#### Output Specification

Output the number of stones they need to drop to move the boulder, while not killing themselves.

#### Sample Input

2
1 1000
1000 4000

#### Sample Output

168
382

• commented on March 19, 2020, 11:27 a.m.

The time limit is now 1 second. Can the problem statement be changed to reflect that?

• commented on April 8, 2019, 2:56 p.m. edited

I am getting WA for all cases in test cases 1-8 and AC for test cases 9 and 10. Could anyone offer an explanation? For all cases I have computed otherwise its outputs the correct answer

• commented on April 8, 2019, 7:57 p.m.

I'm pretty sure your sieve is incorrect

• commented on April 19, 2017, 11:16 a.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Nov. 28, 2014, 7:55 p.m.

Last one's timing out.

• commented on Nov. 28, 2014, 8:09 p.m.

Yes, it is. There are efficient algorithms to find all the primes from to that are much faster than just checking if each number is prime individually. One example is the Sieve of Eratosthenes.

• commented on Dec. 1, 2014, 4:47 p.m.

bam