SHARE
TWEET

Untitled

a guest Jun 19th, 2017 47 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def P10(n):
  2.     r = int(n**0.5)
  3.     assert r*r <= n and (r+1)**2 > n
  4.     V = [n//i for i in range(1,r+1)]
  5.     V += list(range(V[-1]-1,0,-1))
  6.     S = {i:i*(i+1)//2-1 for i in V}
  7.     for p in range(2,r+1):
  8.         if S[p] > S[p-1]:  # p is prime
  9.             sp = S[p-1]  # sum of primes smaller than p
  10.             p2 = p*p
  11.             for v in V:
  12.                 if v < p2: break
  13.                 S[v] -= p*(S[v//p] - sp)
  14.     return S[n]
  15.    
  16. print P10(2 * 10**9)
RAW Paste Data
Top