인프런 커뮤니티 질문&답변

답변 감사합니다.

단락 평가 방식으로 인해 계산 비용이 적은 조건을 앞에 위치시켜야 하는 것은 이해했습니다. 현재 강의 노트에 나와있는 조건은 계산 비용이 비교적 높은 나머지 연산이 앞에 위치해 있으므로 수정이 필요해보입니다.

추가적으로 한가지 더 질문드립니다.

불필요한 연산을 회피하기 위해 i * i > n이라면, 그 이후의 모든 i에 대해서도 나머지 연산을 할 필요가 없다는 것은 이해했지만, 그 이후의 모든 i 에 대한 나머지 연산 뿐만 아니라 첫번째 조건 연산(i * i > n)도 하지 않도록 코드 변경이 필요하지 않을까요?

현재 딩코딩코님이 제안해주신 코드는 두 조건을 만족하는 경우에만 break로 for문을 탈출하기 때문에 prime_list 에있는 모든 i 에 대해서 i * i <= n 조건을 수행해야 합니다.

예를 들어 7이 소수인지 확인하기 위해 i = 3 이후의 i * i <= n 조건을 더이상 수행할 필요가 없지만 현재 딩코딩코님이 제안해주신 코드에서는 i = 3 인 경우 n % i == 0 조건을 만족하지 못하기 때문에 break문으로 for문을 탈출하지 않아 i = 5인 경우의 i * i <= n조건을 검사해야 합니다.

따라서 저는 아래와 같이 코드를 작성해야한다고 생각하는데 어떻게 생각하시나요?

def find_prime_list_under_number(number):
    prime_list = []
    for n in range(2, number + 1):
        is_prime = True
        for i in prime_list:
            if i * i > n:
                break
            if n % i == 0:
                is_prime = False
                break
        if is_prime:
            prime_list.append(n)
    return prime_list

안녕하세요 인프런님!! 우선 확인이 늦어 죄송합니다 ;_; 추가 질문에 대해서 알림이 안오는 구조라서 지금에서야 봤습니다!

1. 교재 이상

엇 그렇네요!!! 교재 부분 변경해뒀습니다 확인 너무너무 감사드립니다!!!!

2. break 문 추가 제안

    

결론부터 말씀드리면, 말씀하신 것처럼 질문자님이 작성하신 코드 방식이 더 효율적인게 맞습니다!! 특히 i * i > n 조건을 먼저 확인하고 바로 반복문을 탈출하는 방식이 시간 복잡도 측면에서 더 나은 구조로 판단됩니다!!

기존 코드에서처럼 n % i == 0 and i * i <= n 순서로 조건을 작성하면, n % i == 0이라는 나머지 연산을 먼저 수행하게 됩니다. 하지만 나머지 연산은 비교적 연산 비용이 높은 편이기 때문에, 먼저 i * i > n을 판단하고 루프를 종료하는 것이 더 효율적입니다!!

또한 질문자님이 지적하신 대로, 어떤 수 n이 소수인지 판단할 때 i * i > n이 되는 시점 이후에는 더 이상 어떤 연산도 수행할 필요가 없습니다. 그런데 기존 코드에서는 n % i == 0이 먼저 평가되기 때문에, 조건에 따라 불필요하게 그 이후 i * i를 계속 계산하거나 다음 i까지도 반복문이 진행될 수 있습니다.

즉, 말씀하신 내용이 맞고, 제가 그 부분을 충분히 고려하지 못했던 것 같습니다.
불필요한 연산을 더 줄일 수 있다는 점에서 제안해주신 방식이 더 효율적이네요.
말씀해주신 방향으로 코드 개선도 고려해보겠습니다!!! 문제의 본질을 정확히 이해하고 성능까지 고려해 개선 방향을 제시하신 점이 인상 깊었습니다. 이런 접근은 이후 다른 알고리즘 문제를 푸실 때도 큰 도움이 될 것 같습니다!! 좋은 질문 너무너무 감사합니다!!! ㅎㅎㅎ

늦게라도 답변해주셔서 감사합니다.