# 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 = 
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 =  * 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