[python] 백준 1978 - 소수 찾기

출처 : 백준, https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

참고 :

에라토스테네스의 체

프로그래머스 - 소수 찾기

 

 

풀이

 

if __name__ == '__main__':
  n = int(input())
  num_set = set(map(int, input().split()))
  max_num = max(num_set)

  if 1 in num_set:
    num_set.remove(1)

  for i in range(2, int(max_num ** 0.5) + 1):
    num_set -= set(j for j in range(i * 2, max_num + 1, i))

  print(len(num_set))

 

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

-