### vaibnak7's blog

By vaibnak7, history, 21 month(s) ago,

Recently I gave Amazon coding test, in which i got the following question

Given n, find all numbers from 1 to n, which are coprime with n.
ex.
Input: n = 5
Output: 4
Explanation — The numbers coprime with n = 5 are (1,5), (2,5), (3,5), (4,5)

Input: n = 10
Output: 4
Explanation — (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 ?

• +6

 » 21 month(s) ago, # |   0 Auto comment: topic has been updated by vaibnak7 (previous revision, new revision, compare).
 » 21 month(s) ago, # |   +1 Basically you have to calculate $\phi(n)$. You can check this for detailed information. https://cp-algorithms.com/algebra/phi-function.html
•  » » 21 month(s) ago, # ^ |   0 ok, so means knowing euler totient function was a prerequisite to solve this question.
 » 21 month(s) ago, # |   +1 There's a cool function called Euler's totient function to calculate that.. this might help : https://en.wikipedia.org/wiki/Euler%27s_totient_function
 » 21 month(s) ago, # |   +6 Your problem could be solved by inclusion-exclusion principle(https://en.wikipedia.org/wiki/Inclusion–exclusion_principle ). It is easier to count numbers that are not coprime to n and not larger than and then substract the answer from n. These numbers are the numbers that share at least one prime divisor with n. To find out how many numbers with this property are in total we do the following: First factorize n in O(sqrtn). Now, knowing all its prime factors (let them be p1,p2,..pk) generate all the subsets of p1,p2,..pk (their number is bounded by the total numbers of divisors of n, so the complexity remains O(sqrtn)).For each subset, let the product of the numbers in it be P. If the subset has an odd number of elements, add n/P else subtract n/P from the answer. To understand why this is correct, think about how many numbers at most equal to n divide a number x, and try to understand how the inclusion exclusion principle works having the sets of numbers that divide each prime divisor of n, and trying to calculate the cardinality of their reunion. A solution that is less general, but can be justified by this approach and may run faster is to compute the Euler Totient function ( https://en.wikipedia.org/wiki/Euler%27s_totient_function ).
 » 21 month(s) ago, # | ← Rev. 2 →   +2 You can also solve it without any knowledge of euler totient using inclusion-exclusion. Coprime pairs = All numbers — (numbers multiple of p1 or numbers multiple of p2 or ...) where pi is the i-thm prime in the prime factorization of n. Ofc, this turns out to be the same thing as calculating the euler totient but you could solve it without knowing about it.
•  » » 10 months ago, # ^ | ← Rev. 3 →   -14 You can use phi function to compute coprime of any number . And if u want to calculate phi of each and every number from 1 to n then you can use phi sieve. Link(https://medium.com/@iamcrypticcoder/calculate-euler-function-using-sieve-dbff3cf82847)
 » 9 months ago, # |   0 you can construct sieve array like below..  public static int[] etf(int n){ int[] dp=new int[n+1]; for(int i=1;i<=n;i++){ dp[i]=i; } for(int i=2;i<=n;i++){ if(dp[i]==i){ for(int j=i;j<=n;j+=i){ dp[j]=dp[j]-(dp[j]/i); } } } return dp; } 
•  » » 3 months ago, # ^ |   0 how you come up with this idea, like dp[j] — dp[j]/i ?
•  » » » 7 weeks ago, # ^ |   0 standard eulertotient function
 » 9 months ago, # |   0 You can find a great explanation in this emaxx article for the O(n log log n) implementation (https://cp-algorithms.com/algebra/phi-function.html), or, if you're feeling crazy you can even do it in linear time, since the totient function is multiplicative. For this I recommend this article: https://codeforces.com/blog/entry/54090
 » 9 months ago, # | ← Rev. 4 →   +1 This a simple question of Euler's totient functionLet $n=p_1^{k_1}\cdot p_2^{k_2}\cdot ... \cdot p_n^{k_n}$ where $p_i$ is prime and $k_i \ge 1$.The answer is $n\cdot \frac{p_1-1}{p_1}\cdot \frac{p_2-1}{p_2}\cdot ... \cdot \frac{p_n-1}{p_n}$The proof is a hard to write but is easy to think of.It can be done in at most $O(\sqrt n)$ time, not sure of the exact time complexity
 » 7 weeks ago, # |   0 but his conrtraint is 10^9 euler phi function will work for 10^6 i guess
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 it is a multiplicative function.
•  » » » 7 weeks ago, # ^ |   0 so are you suggesting segemented sieve method cause I need like an pre computed array of 10^10 numbers
•  » » » » 7 weeks ago, # ^ |   0 You can determine all prime divisors of n in O(sqrt(n)).
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}