Many primes, very fast. Uses primesieve.

## pyprimesieve

Many primes, very fast. Uses primesieve.

primesieve, one of the fastest (if not the fastest) prime sieve implementaions available, is actively maintained by Kim Walisch.

It uses a segmented sieve of Eratosthenes with wheel factorization for a complexity of `O(nloglogn)` operations.

### Performance

Regarding primesieve for C++:

primesieve generates the first 50,847,534 primes up to 10^9 in just 0.4 seconds on a single core of an Intel Core i7-920 2.66GHz, this is about 50 times faster than an ordinary C/C++ sieve of Eratosthenes implementation and about 10,000 times faster than trial-division. primesieve outperforms [Kim’s] older ecprime (fastest from 2002 to 2010) by about 30 percent and also substantially outperforms primegen the fastest sieve of Atkin implementation on the web.

For comparison, on an Intel Core i7 2GHz, `pyprimesieve` populates an entire Python list of the first
50,847,534 primes in 1.40 seconds. It’s expected that a Python implementation would be slower than C++ but,
surprisingly, by only one second.

`pyprimesieve` outperforms all of the fastest prime sieving implementations for Python.

Time (ms) to generate the all primes below one million and iterate over them in Python:

algorithm | time |

pyprimesieve | 2.79903411865 |

primesfrom2to | 13.1568908691 |

primesfrom3to | 13.5800838470 |

ambi_sieve | 16.1600112915 |

rwh_primes2 | 38.7749671936 |

rwh_primes1 | 48.5658645630 |

rwh_primes | 52.0040988922 |

sieve_wheel_30 | 59.3869686127 |

sieveOfEratosthenes | 59.4990253448 |

ambi_sieve_plain | 161.740064621 |

sieveOfAtkin | 232.724905014 |

sundaram3 | 251.194953918 |

It can be seen here that `pyprimesieve` is *4.7 times faster* than the fastest Python alternative using `Numpy` and
*13.85 times faster* than the fastest pure Python sieve.

All benchmark scripts and algorithms are available for reproduction. Prime sieve algorithm implementations were taken from this discussion on SO.

### Functions

**primes(n)**: List of prime numbers up to n.

**primes(start, n)**: List of prime numbers from start up to n.

**primes_sum(n)**: The summation of prime numbers up to n. The optimal number of threads will be determined for the
given number and system.

**primes_sum(start, n)**: The summation of prime numbers from start up to n. The optimal number of threads will be
determined for the given numbers and system.

**primes_nth(n)**: The nth prime number.

**factorize(n)**: List of tuples in the form of (prime, power) for the prime factorization of n.

### Installation

pip install pyprimesieve

**NOTE**: Because of the need to use OpenMP to compile the parallelized version of summation, g++ is specified in
environment variables of setup to avoid distutils choosing a compiler that does not have support for OpenMP. If you
don’t have g++, you will need to pass in a valid compiler as an environment variable.

**NOTE**: For OS X users, g++ is by default linked to clang which does not support OpenMP. This means that you will get a
potentially misleading error while installing. Something like,

ld: library not found for -lgomp clang: error: linker command failed with exit code 1 (use -v to see invocation) error: command 'g++' failed with exit status 1

Just install g++.

Like any C/C++ extension, you need to have the development package of Python (able to include Python.h) in order to compile. On Ubuntu you can simply run,

sudo apt-get install python-dev

After installation, you can make sure everything is working by running the following inside the project root folder,

python tests

### License

“Modified BSD License”. See LICENSE for details. Copyright Jared Suttles, 2015.

## Changes

### 0.1.5 (2015-07-05)

- added to pypi

### 0.1.4 (2013-08-06)

- Parallel prime summation is now a class
- Threads calling callback method are NOT synchronized so faster on large input
- Updated README in bench to reflect new timings (small input is slightly worse but large is twice as fast)

### 0.1.3 (2013-08-05)

- Fixed compilation warnings
- extern “C”
- Added more information regarding installation to README; updated docstring

### 0.1.2 (2013-07-12)

- primes_nth uses callback class instead of creating any PyObjects in order to call primes
- Caused a memory leak and was unnecessary

### 0.1.1 (2013-07-12)

- Distutils setup.py: got multithreaded summation compiling with OpenMP
- Removed all code to manually compile executable
- CC and CXX environment variables set to avoid clang (and other non-openmp compilers) use

- Replaced executable code with parallelized function in the actual extension
- Rewrote primes_sum and primes_nth Python functions in C++ and removed Python script completely

### 0.1.0 (2013-07-06)

- pyprimesieve initial

## Download Files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

File Name & Checksum SHA256 Checksum Help | Version | File Type | Upload Date |
---|---|---|---|

pyprimesieve-0.1.12.tar.gz (32.6 kB) Copy SHA256 Checksum SHA256 | – | Source | Jul 5, 2015 |