Python 소수(Prime Number) 탐색 코드 분석

분석 대상 코드

sum(all(i%j for j in range(2,int(i**.5)+1))for i in range(3,10**6,2))+1

코드의 목적: 1부터 1,000,000까지의 모든 소수(Prime Number)의 개수를 계산합니다.

[1] 상세 개념 5가지

1. 소수 (Prime Number)와 그 판별법

소수란 1보다 큰 자연수 중에서 1과 자기 자신만을 약수로 가지는 수를 말합니다. (예: 2, 3, 5, 7, 11, ...) 어떤 수 N이 소수인지 판별하는 가장 기본적인 방법은 2부터 N-1까지의 모든 수로 나누어 보아, 한 번이라도 나누어떨어지면 소수가 아니라고 판단하는 것입니다.

2. 소수 판별의 최적화 (제곱근 활용)

어떤 수 N의 약수는 N의 제곱근(\sqrtN)을 기준으로 대칭적으로 존재합니다. 만약 N이 두 수 a와 b의 곱(N = a * b)으로 표현된다면, a와 b 중 적어도 하나는 N의 제곱근보다 작거나 같습니다. 이 원리를 이용해, N이 소수인지 판별할 때 2부터 N-1까지 모두 확인할 필요 없이, 2부터 N의 제곱근까지만 나누어 보아도 충분합니다. 코드의 int(i**.5)+1 부분이 바로 이 최적화 원리를 적용한 것입니다. (i**.5는 i의 제곱근을 의미합니다.)

3. 제너레이터 표현식 (Generator Expression)

(표현식 for 항목 in 반복가능객체) 형태로, 대량의 데이터를 한 번에 메모리에 올리지 않고 필요할 때마다 값을 하나씩 생성하는 이터레이터(iterator)를 만듭니다. 이 코드는 두 개의 제너레이터 표현식을 중첩하여 사용합니다.

이 방식을 사용하면 리스트를 직접 만드는 것보다 메모리를 훨씬 효율적으로 사용할 수 있습니다.

4. all() 함수와 불리언(Boolean) 평가

all(iterable) 함수는 인자로 받은 반복 가능한(iterable) 객체의 모든 요소가 참(True)일 때만 True를 반환하고, 하나라도 거짓(False)이 있으면 False를 반환합니다. Python에서는 숫자 0은 False로, 0이 아닌 모든 숫자는 True로 취급됩니다.

따라서 all(i%j for j in ...)는 i가 2부터 자신의 제곱근까지의 어떤 수로도 나누어 떨어지지 않을 때, 즉 i가 소수일 때만 True를 반환합니다.

5. sum() 함수와 최종 계산

sum(iterable) 함수는 반복 가능한 객체의 모든 요소의 합을 구합니다. 이때 불리언 값 True는 숫자 1로, False는 0으로 취급하여 더합니다.

[2] OX 퀴즈 5개

문제 1

이 코드는 1,000,000을 포함하여 소수인지 검사한다.

정답: X
상세 풀이: range(3, 10**6, 2)는 3부터 시작하여 1,000,000 직전(즉, 999,999)까지의 홀수를 의미합니다. `range` 함수의 두 번째 인자는 포함되지 않으므로 1,000,000은 검사 범위에 들어가지 않습니다.

문제 2

코드 마지막에 +1을 하는 이유는 숫자 1을 소수에 포함시키기 위해서이다.

정답: X
상세 풀이: 숫자 1은 소수가 아닙니다. range(3, 10**6, 2)는 3 이상의 홀수만을 대상으로 하므로, 유일한 짝수 소수인 2가 계산에서 빠지게 됩니다. 따라서 마지막에 +1을 하여 2를 개수에 포함시키는 것입니다.

문제 3

i % j 연산 결과가 0이 되는 순간, 해당 i에 대한 all() 함수의 결과는 False가 된다.

정답: O
상세 풀이: i % j가 0이라는 것은 i가 j로 나누어 떨어진다는 의미이며, 이는 i가 소수가 아니라는 증거입니다. Python에서 숫자 0은 `False`로 평가되므로, `all()` 함수는 즉시 `False`를 반환하고 나머지 검사를 중단합니다.

문제 4

for i in range(3, 10**6, 2) 대신 for i in range(2, 10**6)으로 변경해도 코드의 최종 결과값은 동일하다.

정답: O
상세 풀이: range(2, 10**6)으로 변경하면 2부터 모든 정수를 검사하게 됩니다. 2의 경우 `range(2, int(2**0.5)+1)` 즉, `range(2, 2)`가 되어 빈 범위를 순회하므로 `all()`은 `True`를 반환합니다. 4 이상의 짝수들은 항상 2로 나누어 떨어지므로 `all()` 결과가 `False`가 됩니다. 기존 코드는 홀수만 검사하고 `+1`을 했고, 변경된 코드는 2에 대해 `True`를, 나머지 짝수에 대해 `False`를 반환하므로 결과적으로 소수의 개수는 동일하게 계산됩니다. (다만, 짝수까지 모두 검사하므로 효율은 떨어집니다.)

문제 5

이 코드는 100만 개의 불리언 값을 저장할 리스트를 생성하므로 메모리 사용량이 매우 크다.

정답: X
상세 풀이: 이 코드는 리스트가 아닌 제너레이터 표현식을 사용합니다. 제너레이터는 모든 값을 미리 계산하여 메모리에 저장하는 대신, `sum()` 함수가 값을 요청할 때마다 다음 값을 하나씩 생성하여 전달합니다. 따라서 메모리 사용량이 매우 적고 효율적입니다.

[3] 5지선다형 문제 5개

문제 1. 이 코드의 정확한 기능은 무엇인가?

정답: 2번
상세 풀이: `sum()` 함수는 `all()`의 결과가 `True`(즉, 소수인 경우)일 때마다 1씩 더하는 역할을 합니다. 이는 소수의 개수를 세는 것과 같습니다. `range(3, 10**6, 2)`로 3 이상의 홀수 소수를 세고, 마지막에 `+1`로 소수 2를 더해주므로, 결과적으로 1부터 100만까지의 모든 소수의 개수를 구하는 것입니다.

문제 2. int(i**.5)+1을 사용하는 가장 주된 이유는?

정답: 4번
상세 풀이: 어떤 수 N이 소수가 아님을 증명하기 위해서는 2부터 N-1까지 모두 확인할 필요 없이, 2부터 N의 제곱근까지만 확인하면 충분합니다. 이 최적화 기법은 불필요한 반복을 크게 줄여주어, 특히 큰 수에 대한 소수 판별 속도를 비약적으로 향상시킵니다.

문제 3. 숫자 i가 11일 때, 내부 제너레이터 (i%j for j in range(2,int(i**.5)+1))가 생성하는 값들은 무엇인가?

정답: 3번
상세 풀이: `i`가 11일 때, `int(i**.5)+1`은 `int(3.316...)+1` 이므로 `int(3.316...)`은 3, 여기에 1을 더해 4가 됩니다. 따라서 `range(2, 4)`가 되어 `j`는 2와 3이 됩니다. 제너레이터는 `11%2`의 결과인 `1`과 `11%3`의 결과인 `2`를 차례로 생성합니다.

문제 4. 코드에서 all() 함수를 any() 함수로 바꾸면 어떤 의미가 되는가?

정답: 2번
상세 풀이: `any()` 함수는 반복 가능한 객체의 요소 중 하나라도 `True`이면 `True`를 반환합니다. `all(i%j ...)`는 `i`가 소수일 때 `True`를 반환했습니다. 만약 `any(not(i%j) for j ...)` 와 같이 조건을 반대로 하면, `i%j`가 0이 되는(즉, 나누어 떨어지는) 경우가 하나라도 있으면 `True`가 됩니다. 이는 `i`가 소수가 아닌 합성수라는 의미이므로, 결과적으로 합성수의 개수를 세게 됩니다. 문제의 `any(i%j ...)`는 `i`가 2 또는 3의 배수가 아니면 대부분 `True`를 반환하므로 소수/합성수 개수와는 다른 의미가 되지만, 가장 유사한 개념 변화는 '소수'를 판별하던 로직이 '소수가 아님'을 판별하는 방향으로 바뀐다는 것입니다. 질문의 의도에 가장 가까운 답은 2번입니다. (더 정확히 말하면 `sum(any(i%j==0 for j in...))`이 합성수의 개수를 셉니다)

문제 5. 다음 중 주어진 코드의 실행 결과로 sum() 함수에 의해 1이 더해지는(카운트되는) 숫자는?

정답: 4번
상세 풀이: `sum()`에 의해 1이 더해진다는 것은 해당 숫자가 코드의 판별 로직에 의해 소수로 판단되었다는 의미입니다. 따라서 53이 소수로 판별되어 개수가 1 올라갑니다.