문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한사항
- n은 2이상 1000000이하의 자연수입니다.
입출력 예
| a | return |
|---|---|
| 10 | 4 |
| 5 | 3 |
풀이
문제를 풀기 위해서는 <에라토스테네스의 체> 라는 수학적 개념이 필요합니다.
에라토스테네스 체는 말 그대로 전체 배열에 들어있는 모든 숫자를 체로 하나씩 거르면서 소수를 찾아내는 개념입니다. 예컨데 1~10까지 숫자 중 소수를 찾기 위해서 소수가 아닌 1을 제외하고 2부터 시작해서 2를 제외한 2의 배수를 지웁니다. 그 다음 소수 중 가장 작은 수인 3의 배수를 지웁니다. 그 다음 작은 소수인 5의 배수를 지웁니다. 다음 작은 소수인 7의 배수를 지웁니다. 이런식으로 10 이전까지 포함된 모든 소수들로 한번씩 걸러주면 1과 N사이에 있는 모든 소수가 나오게됩니다.
하지만 굳이 모든 소수를 체로써서 거를 필요는 없습니다. 모든 자연수는 소수의 곱으로 표현된다는 원리를 사용하면 모든 소수 대신에 N의 제곱근까지만 지워주면 됩니다. 이경우 10의 제곱근인 3.xxxx의 자연수인 3의 배수까지만 체로 걸러주면 되겠네요.
import math
def solution(n):
result = [v for v in range(2,n+1)] #전체숫자
limit = math.trunc(math.sqrt(n)) #제곱근
count = 2
n = 1
while count <= limit:
result = list(filter(lambda x : count == x or x % count != 0 , result))
count = result[n]
n += 1
return len(result)이를 우직하게 적용해 파이썬코드로 한 번 풀어보았습니다.
우선 전체숫자가 담긴 리스트를 만들고, N의 제곱근도 구해줍니다.
그 다음 '체'에 해당하는 숫자인 count와 count를 늘려나갈 n을 만들어줍니다.
모든것이 셋팅되었으면 while문을 이용해 filter함수를 사용해 하나하나 필터링 해줍니다.
while문 마지막부분에 필터링할 소수를 리스트에서 1씩 인덱스를 증가시키며 전환시켜줍니다.
다른풀이
def solution(n):
num=set(range(2,n+1))
for i in range(2,int(n**0.5)+1):
if i in num:
num -= set(range(i*i,n+1,i))
return len(num)set을 이용한 차집합을 이용해 간결하게 풀어낸 방법입니다. 제 방법과 비교했을 때 시간복잡도도 9배이상 빠르더군요 😭 sqrt를 쓰지않고 int(n**0.5)라는 제곱산술연산자를 사용해 풀어냈습니다. 또한 filter함수대신에 set의 차집합을 통해 제거해나가는 깔끔한 방식입니다. 소수 배수의 집합을 range(i*i,n+1,i)풀어낸것도 인상적이네요. 수학적인 개념과 알고리즘의 깔끔하게 맞아떨어지는 멋진 코드였습니다.
