Finding number of numbers coprime with n in range 1 to n
Difference between en1 and en2, changed 45 character(s)
Recently I gave Amazon coding test, in which i got the following question &mdash;<br/> ↵

Given n, find all numbers from 1 to n, which are coprime with n.

ex.
<br/>↵
ex.<br/>

Input: n = 5
 <br/>
Output: 4
 <br/>
Explanation &mdash; The numbers coprime with n = 5 are (1,5), (2,5), (3,5), (4,5)↵

Input: n = 10

Output: 4 
 <br/>↵
Output: 4 <br/>

Explanation &mdash; (1,10), (3,10), (7,10), (9,10)↵

Constraints  1 <= n <= 10^9.↵

I wrote a brute force solution, where i took each numebr from 1 to n and tried to find its gcd with n. Which apparently gave a TLE on most of the test cases.↵

Can anyone kindly guide me how to solve this problem ?↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English vaibnak7 2019-08-03 15:59:33 45 Tiny change: 'me with n.\nex.\nInp' -> 'me with n.<br/>\nex.\nInp'
en1 English vaibnak7 2019-08-03 15:56:42 653 Initial revision (published)