Source code for tryalgo.primes

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Prime numbers by Eratosthene
nombre premiers <n
jill-jenn vie et christoph durr - 2014-2018
"""


# snip{ eratosthene
# pylint: disable=redefined-outer-name
[docs]def eratosthene(n): """Prime numbers by sieve of Eratosthene :param n: positive integer :assumes: n > 2 :returns: list of prime numbers <n :complexity: O(n loglog n) """ P = [True] * n answ = [2] for i in range(3, n, 2): if P[i]: answ.append(i) for j in range(2 * i, n, i): P[j] = False return answ
# snip} # snip{ gries_misra # pylint: disable=redefined-outer-name
[docs]def gries_misra(n): """Prime numbers by the sieve of Gries-Misra Computes both the list of all prime numbers less than n, and a table mapping every integer 2 ≤ x < n to its smallest prime factor :param n: positive integer :returns: list of prime numbers, and list of prime factors :complexity: O(n) """ primes = [] factor = [0] * n for x in range(2, n): if not factor[x]: # no factor found factor[x] = x # meaning x is prime primes.append(x) for p in primes: # loop over primes found so far if p > factor[x] or p * x >= n: break factor[p * x] = p # p is the smallest factor of p * x return primes, factor
# snip} # pylint: disable=redefined-outer-name, missing-docstring if __name__ == "__main__": # compare the running times and show the ratio between the performances from time import time def test(f, n): start = time() for _ in range(10): f(n) return time() - start print("eratosthene\tgries_misra\tratio") n = 4 for _ in range(30): E = test(eratosthene, n) G = test(gries_misra, n) print("%f\t%f\t%f" % (E, G, G / E)) n *= 2