ETFS - Euler Totient Function Sieve
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?
|
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 |