There are different ways of doing it. Here is my suggestion. We loop over all the numbers from 1 to N and check if their GCD (greatest common divisor) is 1 or not. For making it on the time limits, we need to write the greatest common divisor function efficiently. The Euclid's algorithm suggest a way for finding GCD in logN time. For more info about GCD go here.
No comments:
Post a Comment