Prime Count in a Range

EasyNumber-TheoryPrimesSieve5 hidden tests

A city archivist is auditing a run of consecutively numbered storage lockers and wants to know how many of the locker numbers in a given range are prime, since prime-numbered lockers get a special tamper-seal.

Given two integers L and R, count how many primes lie in the inclusive range [L, R].

Input format

Line 1: two space-separated integers L and R.

Output format

A single integer: the number of primes p with L <= p <= R.

Constraints

1 <= L <= R <= 200000
R - L <= 100000

Examples

Example 1

Input

10 20

Expected

Explanation

Primes between 10 and 20 inclusive are 11, 13, 17, 19 -> count 4.

Example 2

Input

8 8

Expected

Explanation

The single locker 8 is not prime, so the count is 0.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.

Sign in to solve →