문제설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
n은 2이상 1000000이하의 자연수입니다.

접근

소수의 개수를 반환
1부터 입력받은 숫자 n 사이에 있는
n은 2이상 1000000이하의 자연수
소수 구하기 > 에라토스테네스의 체

풀이

에라토스테네스의 체를 사용하고 마지막에 0, 1을 카운트에서 제외함

import math

def solution(n):
  array= [True for i in range(n+1)]
  for i in range(2, int(math.sqrt(n))+1):
    if array[i] == True:
      j= 2
      while i * j <= n:
        array[i*j]= False
        j+= 1
  count= array.count(True)
  return count-2

다른 풀이

파이썬의 집합 자료형을 활용한 풀이로, range의 특성과 세트의 차집합 연산을 사용하여 남은 세트의 len를 구함으로써 시간복잡도를 최소화함

def solution(n):
    num=set(range(2,n+1))

    for i in range(2,n+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return len(num)