language: Python (python 2.7.3)
date: 364 days 12 hours 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*x,N,2*x)) or r)
                  if (x in r) else r), 
               range(3,int((N+1)**0.5+1),2), set([2]+range(3,N,2)))
 
print( sorted( list( primes( 400000 )))[-2:] )
 
# 100k:  time: 0.04s    memory: 5660 kB 
# 200k:  time: 0.07s    memory: 6520 kB
# 400k:  time: 0.13s    memory: 7388 kB
# 1m:    time: 0.30s    memory: 10680 kB    < O(n)    !!!!
# 2m:    time: 0.60s    memory: 16736 kB      n^1.0   !!!
# 4m:    time: 1.23s    memory: 28776 kB    O(n^1.04) !!
set-based one-liner upto SQRT - on ODDS ONLY - difference_update