eolymp
Competitions

DSA Week 2

Primes

Let m and n (2m < n107) be two integers. Consider the following set:

Prime(m, n) = { p | p prime and mpn }.

Find the cardinality of the set Prime(m, n).

Input

Consists of several tests. The input of each test is represented on a single line. Any two consecutive tests are separated by an empty line. For each test, the values for m and n are given on the same line, separated by exactly one space.

Output

For each test, the result will be written on a different line (the tests will have the same order as in the input). The results of any two consecutive tests will be separated by an empty line. For each test, the result will be the cardinal of the set Prime(m, n).

Time limit 10 seconds
Memory limit 256 MiB
Input example #1
4 12

70 110

5 150
Output example #1
3

10

33
Source 2012 ACM SEERC Bucharest, Vinnica