The Torture Chamber

View as PDF

Submit solution

All submissions

Best submissions

Points: 15

Time limit: 1.0s

Memory limit: 64M

Author:

quantum

Problem type

Just when you, Raoul, and the Persian started to celebrate the entry into the "Phantom's house", the boulder closes the entrance. You have been locked inside. You all see yourself in a room, a hexagonal room, with glass walls. The Persian finally realized: this is the Phantom's torture chamber! Inside, you see an iron tree. Wait, it's not just one, not just two, but a forest, thanks to the mirrors. The room starts to heat up. At this rate, you will be toasted very soon.

As he explains: he has seen one all the way back in Mazandaran, Persia, where he was once the chief of police. The Phantom built the Shah of Persia a palace there, a long time ago, long before the construction of this opera house. To please the little Sultana, the Phantom built her a room with mirror walls to create an infinite array of things. However, she got bored pretty quick, so he converted the room into a torture chamber, where the condemned would be placed inside, and the little Sultana would watch, with the Phantom, the death of the poor prisoner from the tortures.

Now, the poor you and your party have fallen victim to this dreaded place. However not all news is bad: the Phantom is out. Raoul managed to talk to Christine, chained inside on the other side of the wall. We discovered that her chains are locked by a combination lock. She also sees two large numbers on her side of the wall. From what Christine sees in the room, we discover that the Phantom doesn't just like prime numbers, nor is just obsessed with Christine or music. The Phantom is also obsessed with prime numbers! Your job is to do the EXACT same thing as before: find the number of primes in the left closed, right open interval. The numbers you get will be used to open the combination lock — which in reality is not a combination lock, but a permutation lock.

But this time, the Phantom, knowing that you like 32-bit computers, decides to make your life more painful, as if the torture chamber is not enough. Since this time, not only is Christine in danger, you, Raoul, and the Persian are all close to being toasted, you have to do this fast: in 1 second!

Input Specification

The input contains two lines. The first line contains number $N$ ~N~, the next line contains $M$ ~M~, where $N, M \in \mathbb N; N, M < 10^{10}$ ~N, M \in \mathbb N; N, M < 10^{10}~. Additionally, $N < M$ ~N < M~ and $M - N \le 2 \cdot 10^7$ ~M - N \le 2 \cdot 10^7~.

Output Specification

Output the combination used to open the permutation lock, i.e. the number of primes in $[N, M)$ ~[N, M)~.

Sample Input 1

1
100

Sample Output 1

Sample Input 2

1
1000000

Sample Output 2

Comments

5

hxxr commented on Aug. 24, 2019, 11:24 p.m.

How come this C solution compiled using Clang passes every case but the exact same C solution but compiled using GCC fails every case?

Seems to me like the GCC submission's output is always one more than the correct answer every time for some reason.

4

c commented on Aug. 27, 2019, 8:18 a.m.

You're probably invoking some obscure undefined behavior and the two compilers are treating them differently.

5

Plasmatic commented on Aug. 26, 2019, 9:30 p.m.

GCC and Clang are different compilers and thus may give different outputs for the same code. My friend had the same issue on Hop Skip Jump a few months ago.

My suggestion is to just submit on the compiler you use locally.

4

drahcirx commented on May 12, 2019, 10:12 p.m.

Are there strings or floats in the input? Why am I getting java.lang.NumberFormatException

4

injust commented on May 12, 2019, 10:48 p.m.

Use a Long; $10^{10} - 1$ ~10^{10} - 1~ will not fit in an Integer.