[구현력 기르기] - 소수의개수(에라토스테네스의 체)

 

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

 

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다. 제한시간은 1초입니다.

 

▣ 입력설명
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

▣ 출력설명
첫 줄에 소수의 개수를 출력합니다.

 

▣  입력예제 1

20

▣  출력예제 1

8

 

 

 

나의 코드

n=int(input())

ch=[1]*(n+1)
cnt=0
ch[0]=0
ch[1]=0

for i in range(2,n+1):
    if ch[i]==1:
        for j in range(2,n+1):
            if i*j >n:
                break
            ch[i*j]=0

print(sum(ch))

에라토스테네스의 체 알고리즘이 리스트 체크 리스트를 사용하여 리스트 인덱스에 대한 숫자를 하나씩 확인하며 소수를 찾으면 그 배수에 해당하는 수들은 모두 체크 하여 카운팅 하는 알고리즘이라고 기억을 한다..!

 

처음 체크리스트를 모두 0으로 초기화 했었지만 최종 소수 갯수를 캐운팅하기 위해 모두 1로 초기화한 이후 소수가 발견되면 그 발견된 소수의 배수를 모두 0으로 초기화 시켰다.

그후 최종적으로 sum 함수를 사용해서 출력 !

 

 

 

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)

 

나와 전체적인 로직은 비슷하나 이중 반복문의 내부 반복문에서 range의 3번째 인자를 사용해서 접근을 한 방법이 달랐다.

이 코드도 기억을 해야겠다~