글 읽기 - python은 시간초과 pypy3는 런타임에러...

chminoo 4년 전 0

시간초과는 아마 소수판별알고리즘을 O(n^0.5)로 만들어서 그런거같긴한데

왜 pypy3는 런타임에러가 날까요?

import sys


def is_prime(n):
    if n % 2 == 0:
        return False
    i = 3
    temp = n**0.5
    while i <= temp:
        if n % i == 0:
            return False
        i += 2
    return True


N = int(sys.stdin.readline())
if N == 2 or N == 5:
    print("yes")
    exit()
temp = str(N)
if '3' in temp or '4' in temp or '7' in temp or temp[0] == '5' or temp[0] == '9' or temp[0] == 8:
    print("no")
    exit()
if is_prime(N):
    k = list(map(str, temp))
    k.reverse()
    for i in range(len(k)):
        if k[i] == '6':
            k[i] = '9'
        elif k[i] == '9':
            k[i] = '6'
    k = int(''.join(k))
    if is_prime(k):
        print("yes")
    else:
        print("no")
else:
    print("no")

jh05013 4년 전 1

현재 BOJ의 Pypy에는 exit이 없어서 sys.exit을 사용해야 합니다. BOJ에서만 보이는 현상으로 알고 있어서 왜 그렇게 되었는지는 모르겠습니다.

chminoo 4년 전 0

아이고 감사합니다 시간초과는 안뜨는데 끝자락에서 틀렸습니다 뜨는걸 보니 예외가 몇개 더있나보네용 열심히 풀어보겠습니다

wider93 4년 전 0

이미 해결하신 것 같지만 한 가지 말씀드리자면

O(n**0.5)가 느리기는 하지만 내부적으로도 불필요한 계산이 많습니다.

위와 같이 짜게 되면 i <= temp를 계산할 때 매번 정수 i와 실수 temp를 비교하게 되어서 타입 변환에 시간을 쓰게 됩니다.

temp를 처음부터 int로 변환해 두고 while 대신 for~range 문으로 대체해본 결과 python으로도 시간 내에 통과합니다.(≈7.7s)

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

문제

문제

출처

ICPC

python은 시간초과 pypy3는 런타임에러...

chminoo 4년 전 0

jh05013 4년 전 1

chminoo 4년 전 0

wider93 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말