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 >

	crazy_8: 2023-12-29 16:41:57 here is my code. I am getting the wrong ans on test case 4. Please help me to solve this [Simes]: do not post code here. Use the forum for this. Last edit: 2024-01-05 16:21:26
	samun_49: 2023-08-28 08:02:19 A really fun problem yet a little frustrating. But really good problem for understanding and applying Segmented Sieve on ETF. I really enjoyed myself. Thanks a lot. If anyone trying this after this date and struggling with WAs. Check overflow and a = 10 to b = 15 you will understand what's going on. Good luck. Last edit: 2023-08-28 08:05:13
	vikas12: 2020-04-17 23:03:54 i am also gettin wa for4 th testcase please help to resolve
	rjsingh_123: 2020-04-14 17:55:10 Getting wrong answer on case 4 Tried multiple times @Francky can you please help on submission 25765715 A small hint would be really helpful :) =(Francky)=> It seems you figured it out by yourself ; well done. Last edit: 2020-04-15 10:25:03
	sanjiuchiha: 2020-04-13 15:10:19 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 25757062. I have generated primes and then used ETF sieve. Please help me. =(Francky)=> You have WA for big inputs. You could check that with any brute force method and a small range. Good luck. Last edit: 2020-04-13 16:35:26
	i_0__0_i: 2020-04-11 10:41:45 99999999899998 99999999999999 -isn't this is a valid test case? but when i use it it takes forever to run!! =(Francky)=> It's a valid test case, you're about to solve it fast. Good luck. Last edit: 2020-04-11 23:33:16
	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 :)

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