primes.py

import math
import timeit


n = 1000000

def primes():
    mark = n * [False]
    ps = [2]
    mark[2] = True
    for x in range(3, n, 2):
        if not mark[x]:
            ps.append(x)
            for m in range(x * x, n, 2 * x):
                mark[m] = True

    return ps

def primo(nump):
    count = 0
    for x in range(2, math.floor(math.sqrt(nump)) + 1):
        if nump % x == 0:
            count = 1
            return False
    if count == 0:
        return True


def primes_lerdo():
    ps = []
    for x in range(2, n):
        if primo(x):
            ps.append(x)
    return ps

print("versão do crivo, O(n * log n * log log n):", timeit.timeit(primes, number=1))
print("versão sem crivo, O(n ** 2):", timeit.timeit(primes_lerdo, number=1))

#print(primes(200000)
#print(sum(ps))
#print(ps[5])
#print(ps[10000])