fork download
  1. from math import log
  2.  
  3. count = 1 ; i = 1 ; D = {}
  4. n = 100000 # 20k:0.20s
  5. m = int(n*(log(n)+log(log(n)))) # 100k:1.15s 200k:2.36s-7.8M
  6. while count < n: # 400k:5.26s-8.7M
  7. i += 2 # 800k:11.21-7.8M
  8. if i not in D: # 1mln:13.20-7.8M (n^1.1)
  9. count += 1
  10. #print(i) ,
  11. #if count%20==0: print ""
  12. k = i*i
  13. if k > m: break
  14. while k <= m:
  15. D[k] = 0
  16. k += 2*i
  17. while count < n:
  18. i += 2
  19. if i not in D: count += 1
  20. if i >= m: print "invalid: top value estimate too small",i,m ; error
  21. print i,m
Success #stdin #stdout 1.14s 8672KB
stdin
Standard input is empty
stdout
1299709 1395639