Welcome, guest | Sign In | My Account | Store | Cart

Generate all prime numbers up to n.

Python, 21 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21``` ```#!/usr/bin/env python def prime(n): """ Generate all prime numbers less than n. """ yield 2 primes = [] for m in range(3,n,2): if all(m%p for p in primes): primes.append(m) yield m def main(): print list(prime(1000)) #or a slower one-liner print [n for n in range(3,1000,2) if all(n%p for p in range(3,n,2))] if __name__=="__main__": main() ```

Rui Ferreira 15 years, 2 months ago

These are not sieves

dth (author) 15 years, 2 months ago

sieve: (verb) to filter a set of elements based on certain criteria

It is NOT the Sieve of Eratosthene, and I apologize for mistagging; but it is indeed a sieve nonetheless.

hasanatkazmi 15 years, 2 months ago

This is sieves.

def getprimes(limit): toreturn = [] numbers = [] for i in range(limit): numbers.append(True) for i in range(2, limit): if numbers[i] == True: toreturn.append(i) numbers[i] = False for j in range(i, limit, i): numbers[j] = False return toreturn

Thomas Ahle 14 years, 5 months ago

A python onliner Sieve:

``````>>> primes = lambda l: l and l[:1]+primes(filter(l[0].__rmod__,l))
>>> primes(range(2,40))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
``````
 Created by dth on Tue, 3 Feb 2009 (MIT)
 ◄ Python recipes (4591) ► ◄ dth's recipes (1) ►

### Required Modules

• (none specified)