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

	surya2196: 2016-03-30 13:39:47 lolypop question
	:.Mohib.:: 2015-11-11 11:50:20 Finally did it.... :) Last edit: 2015-11-11 12:05:11
	Parul Yadav: 2015-09-06 10:15:38 finally AC... feeling good
	Diksha Jaiswal: 2015-06-23 17:22:15 quite a learning problem for me (y) :)
	Daksh: 2015-04-12 19:47:16 Accepted... :) nice problem... Last edit: 2015-04-13 07:17:54
	Kid Algorist: 2015-01-17 17:01:38 Easily understood tricky questions are the best. Big ups to Francky. Hope to see many more such questions in the future. To those getting TLEs and WAs, Don't give up, this question is well worth it. --francky--> Thanks for the appreciation. I really appreciate. --Cheers. Last edit: 2015-01-18 17:49:08
	Walid Amin: 2015-01-02 16:06:20 this problem really taught me how to use sieve in other problems other than generating primes :D NICE PROBLEM --francky--> Thanks for the appreciation. Last edit: 2015-01-02 16:20:29
	rahul goyal: 2014-12-30 12:36:26 okkk...got it (y).. thankss..
	rahul goyal: 2014-12-30 12:17:53 example output should be 1 2 3 4 ??? explain this? --ans(Francky)--> Firstly, it's from 1 to 5 inclusive, so 5 numbers are awaited. Then we have the well known values phi(1)=1, phi(2)=1, phi(3)=2, phi(4)=2 and phi(5)=4. See ETF : the example is exactly the same. Last edit: 2014-12-30 12:25:47
	Yashpal: 2014-12-30 12:17:00 AC in 0.22s !! @Francky Please see my best solution Could I make more optimization ?? By the way nice combination of two problems PRIME1 and ETF ! :P Last edit: 2014-12-30 13:08:58

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