에라토스테네스 (2) 썸네일형 리스트형 [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(*.. [EP003] 큰 수의 소수분해 from typing import List import math from time import time from tqdm import tqdm def get_primes_under_siev(n: int) -> List[int]: root_n = int(math.sqrt(n)) siev = {} siev[0] = siev[1] = 0 siev[2] = 1 for i in range(2, root_n + 1): # print(i) if siev.get(i, 1): for j in range(i + i, n + 1, i): siev[j] = 0 # print(siev) primes = [n for n in range(2, n + 1) if siev.get(n, 1)] return primes def facto.. 이전 1 다음