Counting Special Numbers with Limited Prime Factors

Adleman is fascinated by numbers and recently encountered a challenging problem. For a given positive integer \(A\), he noticed that there exist some natural numbers whose prime factorization does not include any factor greater than \(A\). Such numbers are very special. Given an interval \([N, N+M]\), find the number of natural numbers in this interval whose all prime factors (if any) are \(\leq A\). Note that by convention, 1 is considered valid.

Mathematical Formulation:

For a natural number \(x \geq 1\) (with 1 considered valid), if its prime factorization is \(x = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}\), then \(x\) is special if and only if \(p_i \leq A\) for all \(1 \leq i \leq k\).

inputFormat

The input consists of three positive integers separated by spaces:

• \(A\): the maximum allowed prime factor.
• \(N\): the start of the interval.
• \(M\): the offset such that the interval is \([N, N+M]\).

For example, an input line might be: 2 1 10.

outputFormat

Output a single integer that represents the count of special natural numbers in the interval \([N, N+M]\) whose prime factors (if any) are all \(\leq A\).

sample

2 1 10

4