소수란 무엇인가?
소수(Prime Number)는 1과 자기 자신 외에 어떤 수로도 나누어 떨어지지 않는 수를 의미합니다. 따라서 어떤 수가 소수인지 판별하려면, 1과 그 수 자신을 제외한 나머지 모든 수로 나누어 보고 나누어 떨어지는 경우가 없는지 확인해야 합니다.
1부터 100까지의 소수 구하기
아래 프로그램은 1부터 100 사이의 모든 소수를 찾아 출력합니다. 동작 원리는 다음과 같습니다.
- 바깥쪽 반복문: 0부터 100까지의 숫자를 차례대로 생성합니다.
- 안쪽 반복문: 2부터 바깥쪽 숫자 바로 앞(i-1)까지의 수로 각각 나누어 봅니다.
- 나눗셈 검사: % 연산자(나머지 연산자)를 사용해 나누어 떨어지는지 확인하며, 하나라도 나누어 떨어지면 break 문으로 반복을 중단합니다.
안쪽 범위의 어떤 수로도 나누어 떨어지지 않으면, for-else 구문의 else 블록이 실행되어 해당 숫자가 소수로 판별되어 화면에 출력됩니다.
for i in range(101):
for j in range(2, i-1):
if i % j == 0:
break
else:
print(i)
실행 결과
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(2, int(i**0.5) + 1)로 변경하면 불필요한 나눗셈 연산을 크게 줄여 실행 속도가 향상됩니다. 또한 0과 1은 소수가 아니므로 바깥쪽 반복문을 range(2, 101)로 시작하면 더 깔끔한 코드가 됩니다.