This is a pre-production deployment of Warehouse, however changes made here WILL affect the production instance of PyPI.
Latest Version Dependencies status unknown Test status unknown Test coverage unknown
Project Description

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: To enable the parallelized version of prime summation, you must use a compiler that supports OpenMP. You may need to pass a valid compiler as an environment variable.

Testing

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.6 (2015-07-07)

  • Python 3 support
  • No longer assume g++ in setup.py but rather tries installing with OpenMP and retries if that fails

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
Release History

Release History

0.1.6

This version

History Node

TODO: Figure out how to actually get changelog content.

Changelog content for this version goes here.

Donec et mollis dolor. Praesent et diam eget libero egestas mattis sit amet vitae augue. Nam tincidunt congue enim, ut porta lorem lacinia consectetur. Donec ut libero sed arcu vehicula ultricies a non tortor. Lorem ipsum dolor sit amet, consectetur adipiscing elit.

Show More

0.1.5

History Node

TODO: Figure out how to actually get changelog content.

Changelog content for this version goes here.

Donec et mollis dolor. Praesent et diam eget libero egestas mattis sit amet vitae augue. Nam tincidunt congue enim, ut porta lorem lacinia consectetur. Donec ut libero sed arcu vehicula ultricies a non tortor. Lorem ipsum dolor sit amet, consectetur adipiscing elit.

Show More

Download Files

Download Files

TODO: Brief introduction on what you do with files - including link to relevant help section.

File Name & Checksum SHA256 Checksum Help Version File Type Upload Date
pyprimesieve-0.1.6.tar.gz (34.5 kB) Copy SHA256 Checksum SHA256 Source Jul 7, 2015

Supported By

WebFaction WebFaction Technical Writing Elastic Elastic Search Pingdom Pingdom Monitoring Dyn Dyn DNS HPE HPE Development Sentry Sentry Error Logging CloudAMQP CloudAMQP RabbitMQ Heroku Heroku PaaS Kabu Creative Kabu Creative UX & Design Fastly Fastly CDN DigiCert DigiCert EV Certificate Rackspace Rackspace Cloud Servers DreamHost DreamHost Log Hosting