[백준] 1978번 소수 찾기(with python)

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

1. 내가 작성한 코드

n = int(input())
cnt = 0
num = list(map(int, input().split()))
rmv_list=[]

arr = list(range(1,1001))

for i in range(2,1001):
  for j in range(2,1001):
    if i*j <= 1000:
      rmv_list.append(i*j)
result = set(arr) - set(rmv_list)

for n in num:
  if n in result:
    if n == 1:
      pass
    else:
      cnt += 1

print(cnt)

1~10000까지가 들어있리는 리스트를 만들고 '소수가 아닌 수'를 빼는 과정을 거쳤다.

 

1은 소수가 아닌데, remove를 할 경우 index가 밀리기 때문에 그냥 if문으로 1만 제외하니 답이 금방 나왔다리

 

2. 다른 풀이

n = int(input())
number = list(map(int, input().split()))
cnt = 0

arr = [True] * 1001 #1000이하의 자연수

m = int(1000 ** 0.5)

for i in range(2, m+1):
  if arr[i] == True:
    for j in range(2*i, 1001, i):
      arr[j] = False

result = [i for i in range(2,1001) if arr[i] == True]

for k in number:
  if k in result:
    cnt += 1

print(cnt)

https://gururuglasses.tistory.com/80

[ Algorithm ] 에라토스테네스의 체 ( Python )( 소수를 구하는 방법)

에라토스테네스의 체를 이용한 풀이

 

나의 지식이 설명할 수 있는 깊이가 아니라서,, 위의 링크를 참고하면 좋을 것 같다.