글 읽기 - 에라토스테네스의 체 사용 vs 다른방법

ycj123z 2년 전 0

안녕하세요. 두가지방법에 대해 시간에 관해서 질문드립니다.

빠른 소인수분해 찾기로 에라토스테네스의 체를 사용하라고 블로그에 포스팅 되어있는 글을 봤는데 직접 구현해보니 다른방법이 더 빠르더라구요.

제가 에라토스테네스체 구현을 잘못한건지 아니면 블로그 게시글이 잘못된건지 아니면 특수한 경우에만 빠른건지 궁금합니다.

알려주시면 감사하겠습니다!

# 에라토스테네스이 체 사용
def factorization(n):
    if n == 1:
        return False
    arr = [False, False] + [True] * (n - 1)
    for i in range(2, int(n**0.5) + 1):
        if arr[i] == True:
            for j in range(i * 2, len(arr), i):
                arr[j] = False
    for k in range(n + 1):
        if arr[k] == True:
            while n % k == 0:
                print(k)
                n /= k
    if n != 1:
        print(int(n))
        
        
# 다른방법 사용
def factorization(n):
    if n == 1:
        return False
    for i in range(2, int(n**(1 / 2) + 1)):
        while n % i == 0:
            print(i)
            n /= i
    if n != 1:
        print(int(n))

shjohw12 2년 전 1

에라토스테네스 체의 시간복잡도는 NloglogN 이고 보통 N까지의 소수를 찾을 때 사용합니다

그냥 정수 N 하나를 소인수분해 할 때는 sqrt(N)까지 나눠보면 되니까 당연히 그게 더 빠릅니다

ycj123z 2년 전 0

shjohw12

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

에라토스테네스의 체 사용 vs 다른방법

ycj123z 2년 전 0

shjohw12 2년 전 1

ycj123z 2년 전 0

shjohw12

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말