약수, 배수와 소수 2

4134: 다음 소수

문제

예제

나의 풀이

소수 리스트를 반환하는 함수를 호출해서 풀려고 했던 나의 코드는 런타임 에러(IndexError), 메모리 초과 등이 났는데 왜 그럴까?

def sieve(limit):
    is_prime = [True] * (limit +1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(limit**0.5)+1):
        if is_prime[i]:
            for j in range(i*i, limit+1, i):
                is_prime[j] = False
    return is_prime

n = int(input())

for _ in range(n):
    i = int(input())
    while True:
        is_prime = sieve(i)
        if is_prime[i]:
            print(i)
            break
        i +=1

다른 풀이

값 자체가 소수 인지 아닌지 판별하여 반환하는 함수를 사용하자 문제를 풀 수 있었다. 논리는 같은데 왜 위 코드는 오답처리가 되고 아래 코드는 정답 처리가 되는 걸까?

def sieve(num):
    if num == 0 or num == 1:
        return False
    elif num == 2:
        return True
    
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return False
    else:
        return True

t = int(input())
for _ in range(t):
    n = int(input())
    while True:
        if sieve(n):
            print(n)
            break
        n+=1