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
[Lakshman]: 2014-12-30 06:43:51

@Francky Thanks for the relax time limit. My sieve is not working correctly. I have to look into that, for now somehow manage to get AC.

Abhishek: 2014-12-29 18:38:26

TLE on O(sqrt(n)) ? , How much will do?
--ans(Francky)--> You will have TLE also with O((B-A+1)×N^0.33). You should read again the title.

Last edit: 2014-12-29 19:25:24

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