Skip to content

Home

Jump to bottom
Jorj X. McKie edited this page Jan 25, 2017 · 3 revisions

Elementary Prime Number Routines in Pure Python

Though developed for personal purposes, this may be usefull for others.

Design Principles

Design principles were

  • stay pure Python, but be as performant as possible
  • no hard coded limits for available primes
  • simple user interface: be cli invokable
  • easy to extend

Features

On import, a zipfile containing previously calculated / known primes will be loaded. On object deletion, the array of primes is again zipped and stored back (when changes occurred only). This happens completely without user intervention, i.e. this zipfile will automatically be created and maintained in the user directory.

One can request factorization of arbitrary positive integers, find the next larger prime (twin) for a given number and counts of primes (primes twins) below a given number.

If - while using these functions - it is determined, that the array of "known" primes must be extended, this is automatically done and will only be noticed by extended response time eventually

The underlying class definition primes.Primes is user interfae agnostic. The cli script contains messages in English, but it will look for a tranlation file (extension *.json) on start. The repository contains one with German translations.

Performance Improvements

To reach best performance while being written in pure Python, the following has been done so far:

  1. Use Miller-Rabin-Test for checking primality of integers, when new primes must be found. While this test is a lot faster than the traditional Sieve of Eratosthenes, it has started as a probabilistic test. Negative results ("not a prime") are certain, but positive findings may be false (though with low probability). For the number range we are restricting ourselves to (<= 2**32), there exist options to turn this test into a determinstic one, which we do use.
  2. Use an array array as prime number store instead of normal lists. This is a lot more efficient and also eases storing this array to file (without having to use JSON or pickling).
  3. When looking up primes / prime twins in the array, we use binary search and not the sequence protocol of array. So looking up a prime => n (a given number), our binary search works some like a array.index_less_equal(n), thus providing the lowest available index.
Clone this wiki locally