project euler problem 073

Counting fractions in a range

It is one of the best problems in the first one hundred project Euler problems, I learned a lot of stuff from this problem.

This is the third problem about Farey sequence.  I learned how to solve this problem from wikipedia. It is very simple when one learned the algorithm. It takes 0.3s to find the answer.

Update:  I did not review this problem carefully. Daniel wrote a very good and detailed tutorial for this problem. It has 14 pages! I found a lot of gems in it. I hope everyone who like this problem spending some time to read it. 

The result mentioned is not good enough. For limit 12000,  the time needed is less than 100 ms. For limit=100000, it only need 2 seconds. 

09/24/2017
I tried to solve the problem with mobius inversion formula and find it is very efficient. I learned how to compute the mobius inversion function quickly with sieve after some search from the Internet. For limit = 100000, it only takes 8ms to get the answer! and limit=10000000, the answer can be found in 1.8 second.  I have not tried the sublinear(in the review of this problem) algorithm yet, which is much faster!