The Torture Chamber

View as PDF

Submit solution


Points:20
Time limit:2.0s
Memory limit:64M
Author:

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, thank 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 is danger, you, Raoul, and the Persian are all close to being toasted, you have to do this fast: in 2 seconds!

Input Specification

The input contains two lines. The first line contains number N, the next line contains M, where N, M \in \mathbb N; N, M < 10^{10}. Additionally, N < M and 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).

Sample Input 1

1
100

Sample Output 1

25

Sample Input 2

1
1000000

Sample Output 2

78498

Comments

    There are no comments at the moment.