[Algorithm] 소수 (에라토스테네스 체)

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

<내 답안>

n = int(input())
cnt = 0
for i in range(1, n+1):
    count = 0
    for j in range(1, i+1):
        if i % j == 0:
            count+=1
    if count==2:
        cnt+=1
print(cnt)

출력은 잘 되는데 계속 시간 초과가 떴다.

n = int(input())
list1 = [0]*n
for i in range(2, n+1):
    for j in range(1, i+1):
        if i % j == 0:
            list1[i-1]+=1
print(list1.count(2))

다른 방식으로 다시 풀어보아도 출력은 잘 되지만 여전한 시간 초과..

<모범답안>

n = int(input())
li = [0]*(n+1)  # 인덱스 번호 20까지 만들려면 21개 필요
cnt = 0  # 소수의 개수
for i in range(2, n+1):
    if li[i] == 0:
        cnt+=1
        for j in range(i, n+1, i):
            li[j]+=1
print(cnt)

[에라토스테네스 체] 방식을 이용했어야 한다고 한다.

문제 타이틀에도 떡 하니 쓰여져 있지만 그냥 소수의 다른 의미(?) 정도로 가볍게 넘긴..

인덱스 n까지 총 n+1개 리스트를 만들고, 0으로 초기화 한 후 인덱스 2부터 시작한다.

인덱스에 해당하는 값이 0이면 소수의 개수를 하나 늘리고, 그 때의 인덱스 배수들을 모두 0에서 1로 바꾼다. 즉, 인덱스에 해당하는 값이 0이면 그게 소수인 것이다!