1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
n은 2이상 1000000이하의 자연수입니다.
n | result |
---|---|
10 | 4 |
5 | 3 |
입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
처음에는 n까지의 모든 숫자에 대해서 하나하나 소수인지 아닌지를 판별해보려고 했다. 그래서 다음과 같은 원시적 코드를 짰다.
def solution(n):
answer = 0
for i in range(2, n+1):
mod = 0
for j in range(2, n):
if i % j == 0:
mod += 1
break
if mod == 0:
answer += 1
return answer
논리는 맞지만.. 시간초과로 실패...
찾아보니 범위에 대한 소수 판별에 에라토스테네스의 체 라는 알고리즘을 활용하면 유용하다고 합니다.
위의 알고리즘을 이용해보기로 한다.
그리고 n이 소수인지 판별할 때 n-1까지 나눠볼 필요 없이 n의 제곱근까지만 나눠보면 판별 가능하다는 사실 깨달음.
두번째 시도.
import math
def solution(n):
arr = set(range(2, n+1))
i = 2
while i < int(math.sqrt(n) + 1):
arr -= set([i*k for k in range(2, n//i + 1)])
i += 1
return len(arr)
통과! 는 했지만 소요시간이 3297ms나 된다.
while 반복문을 돌리고, list도 만들어야 돼서 그런가보다.
범위 내의 배수를 어떻게 제거할 수 있을까 고민하다가 저렇게 list를 만들어 집합연산으로 빼준건데, 더 효율적인 방법을 이용한 다른 사람들의 풀이가 있었다.
def solution(n):
arr = set(range(2, n+1))
for i in range(2, n+1):
if i in arr: # 남은 수 중 가장 작은 i
arr -= set(range(2*i, n+1, i))
return len(arr)
Wow!!! 373ms!! 10분의 1로 줄었다.
맨날 쓰는 range함수를 저런 식으로 이용해볼 생각을 못했네..☆
range(start, end, step)
다시한번 복습하면서 끝.