글 읽기 - 시간초과를하다보니 제머리가 초과됐습니다

tlawotjd123 3년 전 1

함수는 에레토스테네스의 체를 이용해 소수를 판별해주는 함수이고,

17번째줄 if조건문에 입력될수의 합으로 이뤄질 두수(a,a-i)가 소수일때 그리고 그차이인 a-i-i가 0보다 클때라는

조건을 설정해두었는데

a-i-i가 0보다커야 출력시 더작은 수부터 출력할수있고 차이가 가장 작아야함으로 for문을 역으로 돌려 조건만족시

출력후 바로 멈추게 하는 그런 코드입니다,,,,

어디서 시간이 드는걸까요 더이상 어디서 줄여야할지 모르겠습니다.

함수는 더이상 건드릴게없는거같고 그이후 for문도 한번밖에안썼는데 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

def sosoo(n) :
    if n == 1 :
        return False
    else :
        for u in range(2,int(n**0.5) + 1) :
            if n % u == 0 :
                return False
    return True

import sys

T = int(input())

for case in range(T) :
    a = int(sys.stdin.readline())
    for i in range(a,1,-1) :
        if sosoo(i) and sosoo(a-i) and a-i-i >=0 :
            print(i,a-i)
            break

ghghgh777 3년 전 1

올려주신 sosoo 함수는 제대로 에라토스테네스의 체 방식을 구현한 것이 아니며, 재호출시 같은 연산을 반복하므로 시간 초과를 피할 수 없습니다.

slah007 3년 전 1

https://www.acmicpc.net/proble...

에라토스테네스의 체는 X 이하의 수 중 소수가 있는지를 X lg lg X에 찾는 알고리즘입니다. 체를 한번만 돌리면 시간 소모 없이 소수 판정이 되므로 실행 시간이 입력한 수의 개수와 상관없게(정확히는 입력시간만 필요) 됩니다.

하지만 위의 구현은 한 수가 소수인지를 sqrt(N)에 찾는 방식이므로 실행 시간에 입력한 수의 개수가 곱해집니다.

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

문제

문제

출처

ICPC

시간초과를하다보니 제머리가 초과됐습니다

tlawotjd123 3년 전 1

ghghgh777 3년 전 1

slah007 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말