ETFS - Euler Totient Function Sieve

Leonhard Euler Totient

In number theory, the totient phi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.


The lonely line in input contains two integers a, b.


Print phi(n) for n from a to b (inclusive).


1 5



0 < a < b < 10^14
b - a < 10^5

Python can get AC under half the time limit (for any test case). My total PY3.4 time is 3.23s for 5 input files.
Have fun ;-)

hide comments
zihadboss: 2020-03-22 23:22:58

Give me hint to solve the problem.
=(Francky)=> Build a sieve specific for totient function.

Last edit: 2020-03-23 18:51:19
ashik_01: 2019-08-08 19:52:13

Just a superb problem. Learned something new. Thanks to the author.

abhinav_jain02: 2018-12-19 13:33:51

I am getting wrong answer on test case 4. I have checked my code multiple times. Can somebody give me a hint.
@Francky ,can you please check my submission 22907703. I have generated primes and then used ETF sieve.
Please help me.
Thank you very much,Francky
Finally found my mistake and got my solution accepted

=(Francky)=> You have some negative outputs for big inputs. Are you sure you well tested you code against brute force totient (no sieve) ?

Last edit: 2019-05-16 16:04:24
eagleshadow: 2018-10-03 16:23:00

Very nice Problem
if you are getting wrong answer just look for the value of phi(10) , ans see if it is 4 or not
you will find the mistake :)

jmr99: 2018-08-16 16:55:46

nice problem!

Last edit: 2018-08-16 21:43:53
yashraj9892: 2018-04-18 19:38:50

can any one tell me Why am i getting sigbus error

jayanth_123: 2017-12-30 11:38:36

Last edit: 2017-12-30 12:13:25
sanki_hu: 2017-05-17 17:39:19

Thanks Francky , Finally AC . Awesome Problem dude. Rank-28
=(Francky)=> I'm glad you liked. You're welcome.

Last edit: 2017-05-17 22:37:58
sanki_hu: 2017-05-17 15:01:45

@Francky Please check my solution id 19424022 .I have done several optimizations and my algo is also correct but i am getting TLE again and again.
=(Francky)=> The goal isn't to sieve the prime numbers, but to sieve totient numbers. Here is the key. Good luck.

Last edit: 2017-05-17 15:33:17
ashishgup: 2017-03-21 00:58:49

Getting internal error. Please fix it.

=(Francky)=> Fixed ; test files were disabled for unknown reason. I'll ask admin if they know...

Last edit: 2017-03-21 07:59:44

Added by:Francky
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64