파이썬 알고리즘 문제풀이 : Section 2-7 / 소수(에라토스테네스 체)

---

문제

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

자연수 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()) # N
# 소수 : 나눠지는 수가 1 과 자신뿐, 1 은 소수 아님
count = 0
for x in range(2, n+1): # 2 부터 N 까지
    for i in range(2, x):
        if x % i == 0:
            break
    else:
        count += 1
print(count)

 

점수

---

강사님 풀이

n = int(input()) # N
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): # i 부터 i 씩 증가 = i 의 배수
            ch[j] = 1
print(cnt)

# 에라토스테네스 체

# 2를 카운트하고, 2의 배수는 모두 지우기, 3을 카운트하고, 3의 배수는 모두 지우기 ...