파이썬 알고리즘 161번 | [백준 1978번] 소수찾기 - 에라토스테네스체

161. 소수찾기

1) 어떤 전략(알고리즘)으로 해결?

에라토스테네스체 복습!

2) 코딩 설명

<내 풀이>

import sys

n=int(sys.stdin.readline().rstrip())
inp=list(map(int, sys.stdin.readline().split()))
cnt=0

lis=[0]*1001
lis[0]=1
lis[1]=1
#1은 소수가 아닌 것
for i in range(2,1001) :
    if lis[i]==0:
        for j in range(i*i,1001,i) :
            #print(lis[:20])
            lis[j]=1
# print(lis[:20])
for i in inp:
    #print(lis[i])
    if lis[i]==0:
        cnt+=1

print(cnt)

<내 틀렸던 풀이, 문제점>

• 에라스토테네스 체를 사용해 풀었는데, 틀린 구석이 있나보다

import sys

n=int(sys.stdin.readline().rstrip())
inp=list(map(int, sys.stdin.readline().split()))
cnt=0

lis=[0]*1001
lis[1]=1
lis[2]=1

for i in range(2,101) :
    if lis[i]==1:
        for j in range(i,101,i) :
            lis[j]=1
for i in inp:
    if i==2:
        cnt+=1
    if lis[i]==0:
        cnt+=1

print(cnt)

=> ㅋㅋㅋㅋ 범위를 2,101 이 아니라 1001!

그리고 1은 소수가 아닌 것 표시하는 것이야
그래서 2는 0으로 놔둬야 하며
range(i, 101, i)
도는게 아니라
range(i*i, 1001,i) 로 돌아야지

<반성 점>

• 복습하자! 에라스토테네스

<배운 점>

• 에라토스테네스의 활용 복습!