Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
7 added 32 characters in body
source | link
def Phi(m, b):
    if not b:
        return m
    if not m:
        return 0
    if m >= 800:
        return Phi(m, b - 1) - Phi(m // primes[b - 1], b - 1)
    t = b * 800 + m
    if not Phi_memo[t]:
        Phi_memo[t] =  Phi(m, b - 1) - Phi(m // primes[b - 1], b - 1)
    return Phi_memo[t]

x = int(input())

if x < 6:
    print [0, 0, 1, 2, 2, 3][x]
    exit()

root2 = int(x ** (1./2))
root3 = int(x ** (1./3))
top = x // root3 + 1
sieve = [0, 0] + [1] * (top - 2)
pi = [0, 0]
primes = []
t = 0

for i in range(2, top):
    if sieve[i] == 1:
        t += 1
        primes.append(i)
        sieve[i::i] = [0] * len(sieve[i::i])
    pi.append(t)

a, b = pi[root3 + 1], pi[root2 + 1]
Phi_memo = [0] * ((a + 1) * 800)

print Phi(x, a) + a - 1 - sum(pi[x // p] - pi[p] + 1 for p in primes[a:b])
def Phi(m, b):
    if not b:
        return m
    if not m:
        return 0
    if m >= 800:
        return Phi(m, b - 1) - Phi(m // primes[b - 1], b - 1)
    t = b * 800 + m
    if not Phi_memo[t]:
        Phi_memo[t] =  Phi(m, b - 1) - Phi(m // primes[b - 1], b - 1)
    return Phi_memo[t]

x = int(input())

if x < 6:
    print [0, 0, 1, 2, 2, 3][x]
    exit()

root2 = int(x ** (1./2))
root3 = int(x ** (1./3))
top = x // root3 + 1
sieve = [0, 0] + [1] * (top - 2)
pi = [0, 0]
primes = []
t = 0

for i in range(2, top):
    if sieve[i] == 1:
        t += 1
        primes.append(i)
        sieve[i::i] = [0] * len(sieve[i::i])
    pi.append(t)

a, b = pi[root3 + 1], pi[root2 + 1]
Phi_memo = [0] * ((a + 1) * 800)

print Phi(x, a) + a - 1 - sum(pi[x // p] - pi[p] + 1 for p in primes[a:b])
def Phi(m, b):
    if not b:
        return m
    if not m:
        return 0
    if m >= 800:
        return Phi(m, b - 1) - Phi(m // primes[b - 1], b - 1)
    t = b * 800 + m
    if not Phi_memo[t]:
        Phi_memo[t] =  Phi(m, b - 1) - Phi(m // primes[b - 1], b - 1)
    return Phi_memo[t]

x = int(input())

if x < 6:
    print [0, 0, 1, 2, 2, 3][x]
    exit()

root2 = int(x ** (1./2))
root3 = int(x ** (1./3))
top = x // root3 + 1
sieve = [0, 0] + [1] * (top - 2)
pi = [0, 0]
primes = []
t = 0

for i in range(2, top):
    if sieve[i] == 1:
        t += 1
        primes.append(i)
        sieve[i::i] = [0] * len(sieve[i::i])
    pi.append(t)

a, b = pi[root3 + 1], pi[root2 + 1]
Phi_memo = [0] * ((a + 1) * 800)

print Phi(x, a) + a - 1 - sum(pi[x // p] - pi[p] + 1 for p in primes[a:b])
def Phi(m, b):
    if not b:
        return m
    if not m:
        return 0
    if m >= 800:
        return Phi(m, b - 1) - Phi(m // primes[b - 1], b - 1)
    t = b * 800 + m
    if not Phi_memo[t]:
        Phi_memo[t] =  Phi(m, b - 1) - Phi(m // primes[b - 1], b - 1)
    return Phi_memo[t]

x = int(input())

if x < 6:
    print [0, 0, 1, 2, 2, 3][x]
    exit()

root2 = int(x ** (1./2))
root3 = int(x ** (1./3))
top = x // root3 + 1
sieve = [0, 0] + [1] * (top - 2)
pi = [0, 0]
primes = []
t = 0

for i in range(2, top):
    if sieve[i] == 1:
        t += 1
        primes.append(i)
        sieve[i::i] = [0] * len(sieve[i::i])
    pi.append(t)

a, b = pi[root3 + 1], pi[root2 + 1]
Phi_memo = [0] * ((a + 1) * 800)

print Phi(x, a) + a - 1 - sum(pi[x // p] - pi[p] + 1 for p in primes[a:b])
6 deleted 266 characters in body
source | link

Python 2 (PyPy 4.0), 2.4253s36961s (Feb 2829 2016)

Official times

Since there was another answer with a similar time, I opted to get more precise results. I timed this 100 times. The score is the following time divided by 100.

real    0m2.387s
user    0m2.199s
sys 0m0.192s

real    0m2.507s
user    0m2.330s
sys 0m0.180s

real    0m2.438s
user    0m2.236s
sys 0m0.205s

real    0m2.348s
user    0m2.180s
sys 0m0.171s

real    0m2.356s
user    0m2.168s
sys 0m0.191s

real    0m2.487s
user    0m2.310s
sys 0m0.180s

real    0m2.371s
user    0m2.198s
sys 0m0.174s

real    0m2.511s
user    0m2.287s
sys 0m0.227s

real    0m2.452s
user    0m2.245s
sys 0m0.210s

real    0m23m56.396s961s
user    0m23m38.219s802s
sys 0m00m18.180s512s

Python 2 (PyPy 4.0), 2.4253s (Feb 28 2016)

Official times

real    0m2.387s
user    0m2.199s
sys 0m0.192s

real    0m2.507s
user    0m2.330s
sys 0m0.180s

real    0m2.438s
user    0m2.236s
sys 0m0.205s

real    0m2.348s
user    0m2.180s
sys 0m0.171s

real    0m2.356s
user    0m2.168s
sys 0m0.191s

real    0m2.487s
user    0m2.310s
sys 0m0.180s

real    0m2.371s
user    0m2.198s
sys 0m0.174s

real    0m2.511s
user    0m2.287s
sys 0m0.227s

real    0m2.452s
user    0m2.245s
sys 0m0.210s

real    0m2.396s
user    0m2.219s
sys 0m0.180s

Python 2 (PyPy 4.0), 2.36961s (Feb 29 2016)

Official times

Since there was another answer with a similar time, I opted to get more precise results. I timed this 100 times. The score is the following time divided by 100.

real    3m56.961s
user    3m38.802s
sys 0m18.512s
5 added 464 characters in body
source | link

Python 2 (PyPy 4.0), 0m 62.240s4253s (Feb 2728 2016)

OP note: I used python2.7 instead of pypy

$ time for i in 1.907e9 1.337e9 1.24e9 6.6e8 9.982e7 4.055e7 2.485e7 41500
> do pypy pi.py <<< $i; done
93875448
66990613
62366021
34286170
5751639
2465109
1557132
4339

real    0m1.696s
user    0m1.360s
sys     0m0.332s

Official times

real    0m2.387s
user    0m2.199s
sys 0m0.192s

real    0m2.507s
user    0m2.330s
sys 0m0.180s

real    0m2.438s
user    0m2.236s
sys 0m0.205s

real    0m2.348s
user    0m2.180s
sys 0m0.171s

real    0m2.356s
user    0m2.168s
sys 0m0.191s

real    0m2.487s
user    0m2.310s
sys 0m0.180s

real    0m2.371s
user    0m2.198s
sys 0m0.174s

real    0m2.511s
user    0m2.287s
sys 0m0.227s

real    0m2.452s
user    0m2.245s
sys 0m0.210s

real    0m2.396s
user    0m2.219s
sys 0m0.180s

Python 2 (PyPy 4.0), 0m 6.240s (Feb 27 2016)

OP note: I used python2.7 instead of pypy

$ time for i in 1.907e9 1.337e9 1.24e9 6.6e8 9.982e7 4.055e7 2.485e7 41500
> do pypy pi.py <<< $i; done
93875448
66990613
62366021
34286170
5751639
2465109
1557132
4339

real    0m1.696s
user    0m1.360s
sys     0m0.332s

Python 2 (PyPy 4.0), 2.4253s (Feb 28 2016)

$ time for i in 1.907e9 1.337e9 1.24e9 6.6e8 9.982e7 4.055e7 2.485e7 41500
> do pypy pi.py <<< $i; done
93875448
66990613
62366021
34286170
5751639
2465109
1557132
4339

real    0m1.696s
user    0m1.360s
sys     0m0.332s

Official times

real    0m2.387s
user    0m2.199s
sys 0m0.192s

real    0m2.507s
user    0m2.330s
sys 0m0.180s

real    0m2.438s
user    0m2.236s
sys 0m0.205s

real    0m2.348s
user    0m2.180s
sys 0m0.171s

real    0m2.356s
user    0m2.168s
sys 0m0.191s

real    0m2.487s
user    0m2.310s
sys 0m0.180s

real    0m2.371s
user    0m2.198s
sys 0m0.174s

real    0m2.511s
user    0m2.287s
sys 0m0.227s

real    0m2.452s
user    0m2.245s
sys 0m0.210s

real    0m2.396s
user    0m2.219s
sys 0m0.180s
4 added 62 characters in body
source | link
3 added 1 character in body
source | link
2 added 117 characters in body
source | link
1
source | link