백준 2581: 소수 Python

 

1. 에러 코드

0부터 10000까지의 수에 대해 소수 여부를 판단할 수 있는 배열을 만든다.

숫자 2의 경우 2의 배수인 4, 6, 8, ... 은 소수가 아니므로 이것을 코드로 구현했다.

이대로 코드를 제출하면 틀리는데,  while 문 때문인 것 같다.

2, 3 등 원래 소수인 숫자는 배열에 체크하면 안되고, 그 다음 배수부터 체크해야 하기 때문에 while문을 돌리기 전 수를 2배 해주고 그 수가 10000이하일 때까지만 돌린다.

하지만 그렇게 하면 2~5000까지만 배수로 소수 체크를 하는 것이기 때문에 5001 부터는 체크되지 않는다.

따라서 while num <= 20000으로 바꿔서 2~10000까지 배수로 소수 체크를 하도록 바꿔봤지만 런타임 에러가 떴다.

M = int(input())
N = int(input())

arr = [0] * 10001   # 소수 배열
for i in range(2, 10001):
    num = i * 2
    while num <= 10000:
        arr[num] = 1
        num += i

result = []
for i in range(M, N+1):
    if arr[i] == 0:
        result.append(i)

if len(result) == 0:
    print(-1)
else:
    print(sum(result))
    print(min(result))

 

 

2. 정답 코드

소수 체크하는 부분을 아래와 같이 바꾸었다.

여기서 주의할 것은 수가 1보다 클 때만 소수 체크를 해야 한다는 것과,

2부터 자기 자신까지 말고 자기 자신보다 1만큼 작은 수까지로 나눈 나머지를 가지고 소수를 따져야 한다.

(num % num == 0이니까 무조건 소수가 아니라고 판단되기 때문)

M = int(input())
N = int(input())

result = []
for num in range(M, N+1):
    check = 0
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                check = 1
                break
        if check == 0:
            result.append(num)

if len(result) == 0:
    print(-1)
else:
    print(sum(result))
    print(min(result))