소수(에라토스테네스 체)

생성일: 2022년 1월 7일 오후 5:17

구현 코드

# 소수(에라토스테네스 체)
import sys
sys.stdin = open("input.txt", "rt")
n = int(input())
numList = [True] * n

# n의 최대 약수는 sqrt(n) 이하이다 => i = sqrt(n)까지 검사
m = int(n ** 0.5)
for i in range(2, m+1):
    if numList[i] == True:
        for j in range(i+i, n, i): # i의 배수들은 소수가 아니기 때문에 전부 False로 수정
            numList[j] = False

primeList = [i for i in range(2,n) if numList[i] == True]

if (n == 2):
    print(1)
else:
    print(len(primeList))

모법 답안

import sys
#sys.stdin=open("input.txt", "r")
n=int(input())
ch=[0]*(n+1)
cnt=0
for i in range(2, n+1):
    if ch[i]==0:
        cnt+=1
        for j in range(i, n+1, i):
            ch[j]=1
print(cnt)

에라토스테네스 체 (소수의 개수를 구하는 수학적 방법)

n까지의 일차원 배열을 만들고 각 인덱스가 소수인지를 검사해야하는 수이다.

이때 모든 칸을 True로 하여서 기본적으로 모든 수가 소수인것으로 간주하고 시작한다. (반대도 가능)

반복문을 돌면서 True를 만나게 되면(소수) 해당 인덱스의 배수들은 모두 소수가 아니게 되기때문에 배수들에 접근하여 배열의 값을 False로 수정한다.

반복문을 한번 다 돌고 마지막까지 True로 남은 인덱스 번호들이 n까지의 수들 중 소수이다.

기억해야 할 점

• 파이썬으로 구현을 할 때 해당 인덱스의 배수 인덱스에 접근하는 코드

for i in range(2, m+1):
	for j in range(i+i, n, i): # i의 배수들은 소수가 아니기 때문에 전부 False로 수정

range()에서 시작점을 i+i (2*i) 로 하여 i의 첫 번째 배수부터 n까지 i만큼 더한 값에 접근한다. == i의 배수에 접근한다.