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

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[소수의 개수]

 

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

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

 

 

*입력 설명

첫 번째 줄에 자연수의 개수 N(2 ≤ N ≤ 200,000)이 주어진다.

 

*출력 설명

첫 번째 줄에 소수의 개수를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_7.txt', 'rt')

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)

# 출력 : 8

 

input_7.txt(입력)

20

 

 

중요내용

1. for j in range(i, n+1, i): 코드에서 range() 함수의 세 번째 인자 i는 시작점(i)부터 끝점(n)까지 숫자를 가져올 때의 스텝을 의미한다.
2. 만약, range(2, 21, 2)이면 2부터 20까지 숫자 중에서 2의 스텝으로 숫자를 가져온다. (ex. 2, 4, 6, ... , 18, 20)