소수(Prime Number)란 무엇인가?
소수는 1과 자기 자신 외에는 어떤 수로도 나누어 떨어지지 않는 자연수입니다. 예를 들어 2, 3, 5, 7, 11 등이 대표적인 소수입니다.
파이썬에서는 %(모듈로, 나머지) 연산자를 사용해 특정 숫자가 다른 숫자로 나누어 떨어지는지 쉽게 확인할 수 있습니다. 나머지가 0이면 나누어 떨어진다는 의미입니다.
1부터 100까지의 소수 찾기 알고리즘
1부터 100 사이의 소수를 찾으려면 범위 내의 각 숫자(x)에 대해, 2부터 x-1까지의 모든 수로 차례대로 나누어 보면서 약수가 있는지 검사해야 합니다. 이 과정은 두 개의 중첩 반복문(nested loop)을 사용하여 구현할 수 있습니다.
for x in range(1,101):
for y in range(2,x):
if x%y==0:break
else:
print (x,sep=' ', end=' ')위 코드를 실행하면 1부터 100 사이의 소수가 출력됩니다.
1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
코드 동작 원리 살펴보기
- 외부 반복문:
range(1, 101)을 통해 1부터 100까지의 숫자를 하나씩 확인합니다. - 내부 반복문: 현재 숫자 x에 대해 2부터 x-1까지의 값(y)으로 나누어 봅니다.
- 나누어 떨어질 경우:
x%y==0조건이 참이면break문으로 내부 반복문을 즉시 종료합니다. 즉, 약수가 존재하므로 소수가 아닙니다.
파이썬만의 독특한 문법: for-else
위 코드에서 주목할 점은 else가 if가 아니라 for 문에 붙어 있다는 것입니다. 파이썬에서는 반복문이 break 없이 정상적으로 끝까지 실행되었을 때 else 블록이 실행됩니다. 따라서 내부 반복문에서 한 번도 나누어 떨어지지 않았다면(약수가 없다면), 해당 숫자 x는 소수이므로 출력됩니다.
성능 개선 팁
위 방법은 가장 직관적인 방식이지만, 효율성을 높이려면 다음과 같은 최적화를 적용할 수 있습니다.
- 제곱근까지만 검사: 약수는 항상 쌍으로 존재하므로, 2부터 x의 제곱근까지만 나누어 보면 충분합니다. 이를 위해
for y in range(2, int(x**0.5)+1)처럼 범위를 줄일 수 있습니다. - 짝수 제외: 2를 제외한 모든 짝수는 소수가 아니므로, 홀수만 검사하면 연산량을 절반으로 줄일 수 있습니다.
- 에라토스테네스의 체: 더 큰 범위의 소수를 빠르게 구하려면 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 활용하는 것이 좋습니다.