We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- All Contests
- ProjectEuler+
- Project Euler #73: Counting fractions in a range
Project Euler #73: Counting fractions in a range
Project Euler #73: Counting fractions in a range
Contest ends in
This problem is a programming version of Problem 73 from projecteuler.net
Consider the fraction, , where and are positive integers. If and , it is called a reduced proper fraction.
If we list the set of reduced proper fractions for in ascending order of size, we get:
It can be seen that there are 3 fractions between 1/3 and 1/2.
How many fractions lie between and in the sorted set of reduced proper fractions with denominator less than or equal to ?
Input Format
The only line of input contains and .
Constraints
Output Format
Output required number of fractions.
Sample Input
2 8
Sample Output
3