Finding number of Coprime Numbers in a specific range

Правка en4, от 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.

Теги #number theory, phi function

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский theFakeFellow 2021-04-07 19:00:54 1 Tiny change: '* where ** _r-l < n_*' -> '* where **_r-l < n_*'
en3 Английский theFakeFellow 2021-04-07 19:00:22 2 Tiny change: '--------\nThanks i' -> '--------\n\nThanks i'
en2 Английский theFakeFellow 2021-04-07 18:59:43 262
en1 Английский theFakeFellow 2021-04-07 18:59:03 204 Initial revision (published)