[EP0010] 백만이하 소수의 합

특정 수 이하의 모든 소수를 구하는 알고리즘을 비교해 보았다.

gen_primes 는 스택오버플로우에서 검색하여 발견한 방법. 에라토스테네스의 방법이 특정수 이하까지의 체를 만들기 위해 메모리를 잡아야 하는 단점이 있는데, 메모리를 덜 잡고 하는 방법이라고 한다. 이해를 하려면 좀 더 들여다 봐야하겠으나, 내 방법보다 훨씬 빠르게 나왔다. (무식하게 메모리 잡고 하는 방법보다는 약간 느렸지만)

커멘트로 써 놓은 테스트 결과는 천만으로 한 것. 백만일 때의 결과는 각각 3.1초, 3.3초, 1.3초, 1.5초. 

import time
import functools


from tqdm import tqdm


def log_elapsed(func):
    @functools.wraps(func)
    def newfunc(*args, **kwargs):
        func_name = func.__name__
        start_time = time.time()
        r = func(*args, *kwargs)
        elapsed = time.time() - start_time
        print(f"{func_name} took {elapsed:.5f} sec")
        return r

    return newfunc


@log_elapsed
def get_primes_sum0(n: int):
    primes = [
        2,
    ]
    sum = 2
    for i in range(3, n):
        is_prime = True
        for p in primes:
            if i % p == 0:
                is_prime = False
                break
            if p * p > i:  # << this condition is crucial
                break
        if is_prime:
            primes.append(i)
            sum += i
        if i % 100000 == 0:
            print(i)
    print(primes)
    print(sum)


@log_elapsed
def get_primes_sum1(n: int):

    primes = [
        2,
    ]
    sum_o_primes = 2
    for i in tqdm(range(3, n, 2)):
        is_prime = True
        for p in primes:
            if i % p == 0:
                is_prime = False
                break
            if p * p > i:  # << this condition is crucial
                break
        if is_prime:
            primes.append(i)
            sum_o_primes += i
        # if i % 100000 == 0:
        #    print(i)
    print(primes)
    print(sum_o_primes)


@log_elapsed
def get_primes_sum_siev0(n: int):
    siev = [1] * n
    siev[0] = siev[1] = 0
    for i in tqdm(range(2, n)):
        if siev[i] == 1:
            for j in range(2 * i, n, i):
                siev[j] = 0
    primes = [i for i in range(n) if siev[i] == 1]
    print(primes)
    print(sum(primes))


def gen_primes():
    """Generate an infinite sequence of prime numbers."""
    # https://stackoverflow.com/a/568618

    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}

    # The running integer that's checked for primeness
    q = 2

    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            #
            yield q
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next
            # multiples of its witnesses to prepare for larger
            # numbers
            #
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1


@log_elapsed
def get_primes_sum_gen0(n: int):
    primes = []
    
    for p in gen_primes():
        if p > n:
            break
        primes.append(p)
    print(primes)
    print(sum(primes))


if __name__ == "__main__":
    n = 10 ** 7
    get_primes_sum0(n)  # 63 sec
    get_primes_sum1(n)  # 68 sec
    get_primes_sum_siev0(n)  # 7 sec
    get_primes_sum_gen0(n) # 15 sec