글 읽기 - 여기 질문을 다 읽어 봤는데 잘 안되네요.

haramel49 2년 전 0

다른분들이 질문해주신 걸 보고 시간복잡도를 최대한 줄여보았는데도 시간초과가 뜹니다.

어떤 분이 항상 소인수분해를 logN의 1/2로 할 수 있는 방법이

가장 작은 소인수로 나누는 방법이 있다고 하여 이렇게 코드를 짜 보았는데 맞는지 모르겠습니다.

제가 어디 부분을 놓치고 있을 걸까요?

import sys

num = int(input())
natural = list(map(int, sys.stdin.readline().split()))

m = max(natural)
sieve = [False, False] + [True] * (m - 1)
for i in range(2, int(m ** 0.5) + 1):
    if sieve[i]:
        for j in range(i + i, m + 1, i):
            sieve[j] = False

for nat in natural:
    i = 2
    while nat != 1:
        if sieve[nat]:
            print(nat, end=' ')
            break
        else:
            if nat % i == 0:
                nat //= i
                print(i, end=' ')
            else:
                i += 1
    print()

haramel49 2년 전 1

제가 생각해봤는데 에라토스테네스의 체에 T, F 값이 아니라, 해당 인덱스 값의 가장 작은 소수값

즉, sieve[10] = 10이라고 한다면 sieve[10]에 F가 아니라 2를 넣어야 하는 건가요?

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

문제

문제

출처

ICPC

여기 질문을 다 읽어 봤는데 잘 안되네요.

haramel49 2년 전 0

haramel49 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말