Project Euler #72: Counting fractions Discussions |

1 year ago+ 1 comment

Python Solution.

lookup=[i for i in range(10**6+1)]
for i in range(2,10**6+1):
    if lookup[i]==i:
        for j in range(i,10**6,i):
            lookup[j]-=lookup[j]//i
for i in range(3,10**6):
    lookup[i]+=lookup[i-1]
t=int(input().strip())
for _ in range(t):
    n=int(input().strip())
    print(lookup[n])

6 months ago+ 0 comments

This was practically identical to my initial approach, but I got a ton of time out errors. So I spent forever trying to optimize and try different approaches, but none of them worked. I saw your comment and tried this way again, and it worked this time. Now it will forever haunt me that I don't know what was different between the first and second attempts.

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge