글 읽기 - 계속 시간초과가 뜹니다.

nmp9981 2년 전 0

에라토스테네스의 체를 개선하여 시간을 어느정도 줄였으나 여전히 계속 시간초과가 뜹니다.

제가 생각하는 이유는 2가지입니다.

1. 체에서 계산시 한번에 출력하지않고 False 변환 따로 소수목록 나열 따로했다

2. 소인수분해 함수에서 2,3,5,7 순서대로 나누었습니다. 순서대로 나누었던것이 문제였다

또 다른 이유가 있나요?

#소인수분해
#소수 리스트 생성
#에라토스테네스의 체
def eratos(y):
  li = [True]*(y+1)
  prime_li = [2,3,5,7]
  i = 3
  while i < 2250:#n**0.5까지의 소수 목록,500만 이하의 소수 판별
    
    if li[i] == True:
      for j in range(i**2, y+1, i):#i^2부터 계산
        li[j] = False
    i += 2#홀수만 계산
  
  for i in range(11, len(li),2):
    if li[i] == True:
      prime_li.append(i)
  return prime_li

#소인수분해
def prime(n, era):
  i = 0
  while n > 1: 
    if n % era[i] == 0:
      n /= era[i]
      print(era[i], end=" ")
    else:
      i += 1
  print()

#입력
t = int(input())
num = list(map(int,input().split()))
era = eratos(5000000)#소수 목록
#각 케이스별 출력
for i in range(0,t):
  prime(num[i], era)

자연수가 100만개, 하나당 크기가 최대 500만까지 들어오기 때문에 쿼리당 logN에 항상 소인수분해를 출력하는 방법을 생각해봅시다. (N은 주어진 자연수)
에라스토체네스의 체에 그 자연수의 소인수중 가장 작은소인수를 저장하면 항상 logN에 소인수분해할수 있습니다. n=sieve[n]으로 탐색하면, 한번에 최대 1/2씩 곱해지기 때문에
logN에 효율적으로 소인수분해가 가능합니다

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

문제

문제

출처

ICPC

계속 시간초과가 뜹니다.

nmp9981 2년 전 0

djs100201 2년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말