[파이썬 알고리즘] 소수(에라토스테네스 체)

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

📄 문제

자연수 N이 입력되면 1부터 N까지의 소수의 개수를출력하는 프로그램을 작성하세요.
만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.
제한시간은 1초입니다.

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

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

▣ 입력예제
20

▣ 출력예제
8

🧞 풀이

풀이 (시간 초과)

# 입력: 첫 줄 - 자연수의 개수 n
# 출력: 소수의 개수 출력

from math import sqrt               # math 패키지에서 제곱근 구하는 sqrt 모듈 불러오기

n = int(input())                    # 정수 n 입력 및 할당

cnt = [0] * (n+1)                   # n+1개 만큼의 0을 담는 리스트 cnt 할당

for i in range(2, int(sqrt(n))+1):  # 2부터 n의 제곱근 + 1까지 반복
    for j in range(2, n+1):         # 2부터 n까지 반복
        if i != j and j % i == 0:   # i와 j가 서로 다르면서, i를 j로 나눈 나머지가 0일 때,
            cnt[j] = 1              # cnt[j]의 값을 1로 변경
print(cnt.count(0)-2)               # cnt의 0의 갯수 - 2를 출력 (cnt[0]과 cnt[1]은 0과 1이기 때문에 빼줘야 함)

 

다른 사람 풀이

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

n = int(input())                        # 정수 n 입력 및 할당
ch = [0] * (n+1)                        # n+1개 만큼의 0을 담는 리스트 ch 할당
cnt = 0                                 # 갯수 세기 위한 cnt 할당

for i in range(2, n+1):                 # 2부터 n까지 반복
    if ch[i] == 0:                      # ch[i] 가 0일 때,
        cnt += 1                        # cnt 1 더해주기
        for j in range(i, n+1, i):      # i부터 n까지 i의 간격으로 (배수들을 확인할 수 있음)
            ch[j] = 1                   # 배수에 해당하는 j일 경우, 1로 ch[j] 값 변환

print(cnt)                              # cnt 값 출력