0

Maybe it is a stupid question, but i was wondering if you could provide the shortest source to find prime numbers with Python. I was also wondering how to find prime numbers by using map() or filter() functions. Thank you (:

EDIT: When i say fastest/shortest I mean the way with the less characters/words. Do not consider a competition, anyway: i was wondering if it was possible a one line source, without removing indentation always used with for cycles. EDIT 2:The problem was not thought for huge numbers. I think we can stay under a million( range(2,1000000) EDIT 3: Shortest, but still elegant. As i said in the first EDIT, you don't need to reduce variables' names to single letters. I just need a one line, elegant source. Thank you!

user1068051
  • 217
  • 1
  • 4
  • 12

4 Answers4

11

The Sieve of Eratosthenes in two lines.

primes = set(range(2,1000000))
for n in [2]+range(3,1000000/2,2): primes -= set(range(2*n,1000000,n))

Edit: I've realized that the above is not a true Sieve of Eratosthenes because it filters on the set of odd numbers rather than the set of primes, making it unnecessarily slow. I've fixed that in the following version, and also included a number of common optimizations as pointed out in the comments.

primes = set([2] + range(3, 1000000, 2))
for n in range(3, int(1000000**0.5)+1, 2): primes -= set(range(n*n,1000000,2*n) if n in primes else [])

The first version is still shorter and does generate the proper result, even if it takes longer.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • You put a two outside your initial list of candidates, and skipped ahead to odds only...smart. But...what's with `primes -= set(... `? Is that a self discarding set? – yurisich Feb 16 '12 at 01:21
  • @Droogans, `primes -= set` is subtracting one set from another. The range expression generates all the multiples of n up to 1000000. – Mark Ransom Feb 16 '12 at 01:42
  • I've made your code a one-liner =) http://stackoverflow.com/a/10640037/711085 : `reduce((lambda r,x: r-set(range(2*x,N,x))), [2]+range(3,int(N**.5),2), set(range(2,N)))` – ninjagecko May 17 '12 at 17:16
  • this can be `primes=set([2]+range(3,1000000,2))` and then `for n in range(3,1000,2): primes -= set(range(n*n,1000000,2*n))`. – Will Ness May 18 '12 at 12:00
  • You would probably prefer to do `if n in primes: primes.difference_update(range(...))`. – ninjagecko May 18 '12 at 13:49
  • @WillNess, I just tried timing it. The original took 2.4 seconds, converting to a true sieve brought it to 1.6 seconds, and adding the other optimizations took it down to 0.6 seconds. – Mark Ransom May 19 '12 at 19:44
1

Since one can just cut and paste the first million primes from the net:

map(int,open('primes.txt'))

This is a somewhat similar to the question I asked yesterday where wim provided a fairly short answer:

is this primes generator pythonic

Community
  • 1
  • 1
Rusty Rob
  • 16,489
  • 8
  • 100
  • 116
0

Similar to the above, but not as cheeky as Robert King's answer:

from itertools import ifilter, imap
def primes(max=3000):
    r = set(); [r.add(n) for n in ifilter(lambda c: all(imap(c.__mod__, r)), xrange(2, max+1))]; return sorted(r)
michaelfilms
  • 704
  • 3
  • 5
0

This uses more characters, but it's readable:

def primes_to(n):
    cands = set(xrange(2, n))
    for i in xrange(2, int(n ** 0.5) + 1):
        for ix in xrange(i ** 2, n, i):
            cands.discard(ix)
    return list(cands)

EDIT

A new way, similar to the above, but with less missed attempts at discard:

def primes_to(n):
    cands = set(xrange(3, n, 2))
    for i in xrange(3, int(n ** 0.5) + 1, 2):
        for ix in xrange(i ** 2, n, i * 2):
            cands.discard(ix)
    return [2] + list(cands)
yurisich
  • 6,991
  • 7
  • 42
  • 63