SPOJ.com - Problem ETFS

ETFS - Euler Totient Function Sieve

#totient

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 ;-)

Submit solution!

hide comments

< Previous 1 2 3 Next >

	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
	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

Submit solution!

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