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
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.
|
|
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
|
|
rahul goyal:
2014-12-30 12:36:26
okkk...got it (y)..
|
|
rahul goyal:
2014-12-30 12:17:53
example output should be
|
|
Yashpal:
2014-12-30 12:17:00
AC in 0.22s !!
|
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 |