Project Euler 72 - Counting Fractions

Official link:

Thought Process

Here I will show you the power of rewording a problem, we are looking for all the proper reduced fractions n/d from 1 to 1,000,000 where n<d and gcd(n,d) = 1, in other words "the number of numbers less than n which are relatively prime to n" see the similarity with Problem 69? This is the exact definition of φ(n)! So all we need to do is find the sum of φ(n) from 2 to 1,000,000.

Using my prime divisor function this code takes ~40 seconds

Interactive Code

Enter an integer (yourinput)

Code will output the number of reduced proper fractions for d <= yourinput