소수 구하기

일반적인 방법으로 1~n (n : 구하고자 하는수) 를 소수로 나눠지는지 n % i  이런식으로 구하면 대략 O(n)의 시간이 걸린다

그런데 n의 제곱근 까지 구한후 나머지가 1보다 큰수를 저장하면 모든 소수를 구할수 있다 대략 O(제곱근(n)) 시간이 걸리는데

코드를 살펴보자

import math


def factor_simple(n):
    arr = []
    if n >= 10:
        sqrtn = int(math.sqrt(n)) + 1
    else:
        sqrtn = n
    for div in range(2, sqrtn):
        while n % div == 0:
            n //= div
            arr.append(div)
    if n > 1:
        arr.append(n)
    return arr


n = int(input())
for i in factor_simple(n):
    print(i)

이 방식말고도 에라토스테네스 체의 소수구하는 방법으로 구할수 있다