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.

Input

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

Output

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

Example

Input:
1 5

Output:
1
1
2
2
4

Constraints

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
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
awesomeabhinav: 2016-12-29 13:23:16

My solution id is 18481441, Got AC but need much more faster algorithm. PLS suggest another efficient way to do this problem

=(Francky)=> You have a good algorithm, you can only work on your constant.

Last edit: 2016-12-31 09:48:59
ashish22_dwd: 2016-10-13 15:32:00

Nice Problem..


Added by:Francky
Date:2014-12-29
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ETF