language: Python (python 2.7.3)
date: 389 days 1 hour ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13

def primes(N):
 return reduce((lambda r,x: (r.difference_update(range(x**2,N,x)) or r) if (x in r) else r), 
               # range(2,N), set(range(2,N)))
               range(2,int((N+1)**0.5+1)), set(range(2,N)))
 
print( sorted( list( primes( 100000 )))[-2:] )
 
#                - SQRT -                                 - NO SQRT -
# 100k: time: 0.06s    memory: 5924 kB                     0.12 7.1
# 200k: time: 0.11s    memory: 7232 kB     < O(n) !!       0.24 9.6
# 400k: time: 0.20s    memory: 9536 kB     < O(n) !!       0.46 14.3
# 1m:   time: 0.48s    memory: 16656 kB    < O(n) !!!      1.12 28.4
# 2m:   time: 0.97s    memory: 28752 kB      O(n) !!!