문제

문제1) 소수 (중등1)

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최소값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최소값은 61이 된다.

입력

첫 째 줄에 M이, 둘째 줄에 N이 주어진다. M과 N은 10000이하의 자연수이며 M은 N보다 같거나 작다.

입력 예시

60
100

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최소값을 출력한다.

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

출력 예시

620
21

문제 풀이

나만큼 복잡하게 푼 사람은 없다고 생각한다.
문제를 풀기 전에 찾아보니, 소수 구하는 방법으로 에라토스테네스의 체라는 방식을 통해 소수를 쉽게 구할 수 있다.

일단 나는 해당 방법으로 풀려고 하긴 했는데, 잘 되지가 않아서 하나씩 뜯어보며 풀었던 것 같다.

m = int(input())
n = int(input())

def create_Numlist(m,n):
    numlist = []
    for num in range(m,n+1):
        numlist.append(num)
    return numlist

def prime_list(m,n):
    primeList = create_Numlist(m,n)
    max = int(n**0.5)
    for i in range(len(primeList)):
        for j in range(2,max+1):
            if primeList[i] % j == 0 and primeList[i] / j != 1 or primeList[i] == 1:
                primeList[i] = 0
    remove_set = {0}
    primeList = [i for i in primeList if i not in remove_set]
    return primeList

def total_sum(numList):
    total = 0
    for i in range(len(numList)):
        total += numList[i]
    return total

primeList = []
primeList = prime_list(m,n)

print(total_sum(primeList))
print(primeList[0])

원래는 primeList 라는 것을 하나 만들어서 값을 추가하려고 했는데, 이게 잘 안되서 그냥 0으로 전부 값을 변경한 다음에 0인 값을 빼는 방식으로 진행하였다.

일단 소수를 구하기 전, 모든 값을 전부 다 나누는 건 비효율적이므로
max 값이 100이라고 가정했을때, x * x가 100이 넘지 않는 수를 먼저 찾아주었다. (max = int(n**0.5))

문제를 풀고 정답을 내다보니까, m = 1 , n = 500 인 케이스에서 자꾸 오류가 나서 확인해보니 2~22 사이의 값의 소수가 포함이 되지 않는 것을 확인하였다.
이에 해당 값을 넣어주기 위해서 primeList[i] / j != 1의 값을 넣어주었다.

해당 값을 넣어주고, 1에 대한 예외처리까지 진행해주니 통과!

def prime_list(m,n):
    primeList = create_Numlist(m,n)
    max = int(n**0.5)
    for i in range(len(primeList)):
        for j in range(2,max+1):
            if primeList[i] % j == 0 and primeList[i] / j != 1 or primeList[i] == 1:
                primeList[i] = 0
    remove_set = {0}
    primeList = [i for i in primeList if i not in remove_set]
    return primeList

뭔가 더 쉽고 간단하게 풀 수 있을 것 같은데, 이렇게 생각이 도달하는 것까지도 좀 골머리를 쌓은 것 같다. 흠.. 어떻게해야 조금 더 간결하게 풀 수 있을지 고민해봐야겠다.