Finding number of Coprime Numbers in a specific range

Revision en4, by theFakeFellow, 2021-04-07 19:00:54

How to find how many numbers in range [l, r] are coprime to n where r-l < n? [ in O(sqrt(n)) complexity]


Thanks in advance.

Tags #number theory, phi function

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English theFakeFellow 2021-04-07 19:00:54 1 Tiny change: '* where ** _r-l < n_*' -> '* where **_r-l < n_*'
en3 English theFakeFellow 2021-04-07 19:00:22 2 Tiny change: '--------\nThanks i' -> '--------\n\nThanks i'
en2 English theFakeFellow 2021-04-07 18:59:43 262
en1 English theFakeFellow 2021-04-07 18:59:03 204 Initial revision (published)