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 >

	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
	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..
	ASHUTOSH DWIVEDI: 2016-07-08 15:29:40 AWESOME FRANCKY....... U ALWAYS MAKE NICE QUESTIONS :) =(Francky)=> You're welcome. Last edit: 2016-07-09 12:32:48
	nightwolf_9197: 2016-05-22 11:16:04 good question but time limit must be constrained to 1 sec =(Francky)=> I prefer when a problem is solvable with almost all languages, Python here should be allowed. It need more times to process. As it is often easier to code in Python, my problems need a good Python script to get AC, and then a poorer C code can get AC. If I could choose, I'll set several time limits ; but it would be very very difficult to maintain/set. And in the future unstable. We yet had a pyramid/cube migration with some tasks... I hope everybody take pleasure and learn in solving tasks, whatever is the proposed time limit, and the time limit you think honest for your own language and skills. You're welcome. Last edit: 2016-05-23 14:26:58
	shivucoder55: 2016-05-01 13:28:07 @Francky .. My solution ID is 16849109 .... It is giving correct answers for all test cases ... But I m getting runtime error (SIGFPE) ... Please give me hint ... Thanks =(Francky)=> You should debug your code on harder test cases than sample. You have AC on one input file, but 'Runtime error' on another. Good luck. Last edit: 2016-05-01 19:46:41

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