<aside>
💬 lv1, 탐색, 에라토스테네스의 체
주어진 정수 N에 대해, 1부터 N까지의 숫자 중 소수의 개수를 찾는 코드를 작성해주세요. 소수는 1과 자기 자신만을 약수로 가지는 1보다 큰 양의 정수입니다.
| 입력 (N) | 출력 (소수의 개수) |
|---|---|
| 10 | 4 |
| 5 | 3 |
첫 번째 예시에서 1부터 10까지의 소수는 2, 3, 5, 7 이므로 총 4개입니다. 두 번째 예시에서 1부터 5까지의 소수는 2, 3, 5이므로 총 3개입니다.
</aside>
def solution(N): **#1 함수 정의**
prime = [True] * (N + 1) **#2 소수 여부 리스트 생성**
prime[0] = prime[1] = False **#3 0과 1의 소수 여부 갱신**
p = 2 **#4 탐색 숫자 p 정의**
while p * p <= N: **#5 while 문 실행 조건 정의**
if prime[p]: **#6 탐색 조건 정의**
for i in range(p * p, N + 1, p): **#7 소수가 아닌 숫자 범위 정의**
prime[i] = False **#8 소수 여부 갱신**
p += 1 **#9 탐색 숫자 p 갱신**
return sum(prime) **#10 sum 함수 적용**
함수 정의
코드의 첫 부분에서 solution이라는 함수를 정의합니다. 이 함수는 하나의 인자 N을 받습니다. N은 1~N 숫자 중 소수를 찾기 위해 입력되는 숫자입니다.
소수 여부 리스트 생성
0 ~ N까지의 숫자의 소수 여부를 초기화하기 위해 0을 포함한 숫자 개수 N+1 만큼 True를 생성해 줍니다. 그렇게 N+1개의 True가 존재하는 리스트를 prime이라는 변수에 할당해 줍니다. 0~ N까지의 각 숫자는 prime의 인덱스에 해당하고 각 숫자의 소수 여부를 True로 초기화합니다.
0과 1의 소수 여부 갱신
0과 1은 자기 자신만 포함하므로 소수가 아닙니다. 그러므로 0과 1 각각 소수 여부 prime[0], prime[1]을 False로 갱신합니다.
탐색 숫자 p 정의
0, 1을 제외한 상태로 소수 여부를 탐색하기 위해 최초 탐색 숫자 2를 p라는 변수에 할당합니다.
while 문 실행 조건 정의
while 문에서는 조건이 False가 될 때까지 회문을 반복합니다. while 문에 들어갈 조건으로 탐색 숫자 p의 제곱이 N보다 작거나 같아야 합니다.
탐색 조건 정의
while 문 아래에서 prime과 p를 이용하여 탐색 조건을 정의합니다. 탐색 숫자 p는 prime의 인덱스로 사용되며 인덱싱하여 나온 값은 탐색 숫자 p의 소수 여부입니다. 탐색 조건으로 탐색 숫자가 소수여야 합니다. 코드로 표현하자면 if prime[p]:로 나타낼 수 있고, 이는 탐색 숫자 p의 소수 여부가 True인 경우를 탐색 조건으로 정의합니다.
소수가 아닌 숫자 범위 정의
소수가 아닌 숫자의 범위를 p를 기준으로 정의합니다. 해당 범위는 p의 제곱을 시작으로 N까지를 p만큼의 간격으로 하는 범위가 됩니다. 해당 범위의 숫자들은 for 문을 돌면서 i라는 변수에 할당됩니다.
소수 여부 갱신
p의 제곱에서 p만큼의 간격으로 이동하면서 N까지의 숫자 i를 prime의 인덱스로 활용하여, 각 탐색 숫자의 소수 여부를 False로 갱신합니다.
탐색 숫자 p 갱신
탐색 숫자 p에 1을 더해주어 p를 갱신합니다.
sum 함수 적용
sum 함수 적용 시, True는 1로 False는 0으로 되어 소수의 개수를 구할 수 있습니다. 이렇게 구한 소수의 개수를 반환합니다.
에라토스테네스의 체
개념: 에라토스테네스의 체는 고대 그리스의 수학자인 에라토스테네스가 소수를 효율적으로 구하기 위해 제안한 방법입니다. 에라토스테네스의 체가 소수를 구하는 방식은 가장 먼저 오는 소수를 구하고 그 소수의 배수가 되는 수를 체로 거르듯이 소거합니다. 그리고 그다음으로 오는 소수를 구하면 마찬가지로 그 소수의 배수가 되는 수를 소거합니다. 이렇게 소수의 배수를 소수가 아닌 수로 걸러내어 다음 소수를 탐색하는 비용을 줄입니다.
인덱싱
