[공부] 소수의 개수 세기 - 에라토스테네스의 체

에라토스테네스의 체

소수의 성질을 관찰해보면 소수가 가진 약수는 1과 자기 자신뿐이라는 것을 알 수 있습니다. 바꾸어 말하면 1과 자기 자신을 제외한 약수가 있다면 그 수는 소수가 아닙니다.

따라서 소수를 알아낸 뒤에는 해당 소수로 나누어떨어지는 모든 수를 소수에서 배제할 수 있습니다.

<풀이 방법>
1. input()으로 n을 받는다. (n개까지의 수 중 소수 개수 찾기)
2. 배열을 만들어서 일단 초기값 True를 준다. (모두 소수라고 치고 초기화)
3. count = 0 초기화 하여 소수개수 count로 넘겨주기
4. for문으로 2부터 n+1까지 돌면서
(0과 1은 소수가 아님!_ 1과 자기자신 2개의 약수를 가져야 소수이므로)
5. 조건문으로 array[i] == True일때만 (즉, 소수일때만)
6. i를 제외한 i의 배수를 제거시켜준다. 따라서 j=2 부터로 설정
7. 반복문 조건으로 배수의 값이 n이하일 때,
array[i*j]를 false로 바꾼다. (i의 배수는 소수가 아니므로)
그리고 j를 증가시키면서 i의 배수를 모두 제거한다.
8. 다시 for문을 돌면서 조건문안에 array[i]가 True = 소수일때 count += 1을 해주어 count의 값을 출력하면 소수의 개수가 나온다.

파이썬 풀이

n = int(input())
array = [True for i in range(n+1)] # 배열안에 초기값으로 True주기
count = 0

# 에라토스의 체
for i in range(2, n+1):
    if array[i] == True:
        j = 2 # i를 제외한 i의 모든 배수 제거
        while i * j <= n:
            array[i*j] = False
            j += 1

for i in range(2, n+1):
    if array[i]:
        count += 1
print(count)