fork(11) download
copy 
  1. # count primes less than or equal to n
  2.  
  3. from random import randint
  4.  
  5. def primes(n):
  6.     b, p, ps = [True] * (n+1), 2, []
  7.     for p in xrange(2, n+1):
  8.         if b[p]:
  9.             ps.append(p)
  10.             for i in xrange(p, n+1, p):
  11.                 b[i] = False
  12.     return ps
  13.  
  14. ps = primes(3163)[1:]
  15.  
  16. sieve = [True] * 500
  17.  
  18. def count(lo, hi):
  19.     for i in xrange(500):
  20.         sieve[i] = True
  21.     for p in ps:
  22.         if p*p > hi: break
  23.         q = (lo + p + 1) / -2 % p
  24.         if lo+q+q+1 < p*p: q += p
  25.         for j in xrange(q, 500, p):
  26.             sieve[j] = False
  27.     k = 0
  28.     for i in xrange((hi - lo) // 2):
  29.         if sieve[i]: k += 1
  30.     return k
  31.  
  32. piTable = [0] * 10000
  33.  
  34. for i in xrange(1, 10000):
  35.     piTable[i] = piTable[i-1] + \
  36.         count(1000 * (i-1), 1000 * i)
  37.  
  38. def pi(n):
  39.     if type(n) != int and type(n) != long:
  40.         raise TypeError('must be integer')
  41.     if n < 2: return 0
  42.     if n == 2: return 1
  43.     i = n // 1000
  44.     return piTable[i] + count(1000 * i, n+1)
  45.  
  46. print pi(1000) # 168
  47. print pi(10000) # 1229
  48. print pi(6543223) # 447519
  49. print pi(9999999) # 664579
  50.  
  51. x = 0
  52. for i in xrange(1000):
  53.     x = x + pi(randint(2,10000000))
  54. print x
Success #stdin #stdout 5.87s 11008KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
168
1229
447519
664579
342649168
https://ideone.com/O9ySi8
language:
Python (cpython 2.7.16)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!