프로그래머스 LV1 소수 찾기(연습문제)
프로그래머스 lv1 소수 찾기(연습문제)
문제 설명
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를 반환
접근
소수 찾기는 에라토스테네스의 체를 이용해야한다.
풀이
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(2*i, n+1, i))
return len(num)
소수의 개수를 반환해야 한다. n을 입력받으면 n까지 소수가 몇개 있는지를 세는 것.
숫자 셋을 num으로 지정하고, n의 최대 약수가sqrt(n)이하이므로int(n**0.5)+1까지 검사를 해준다.
range(start, stop[, step]) -> range object
Return an object that produces a sequence of integers from start (inclusive)to stop (exclusive) by step.
step이 주어지면 start에서 step 만큼 증가한다. 즉set(range(2*i, n+1, i))를 통해서 i의 배수들을 다 제거해주는 것이다.
set 함수를 쓴 이유는 리스트끼리는 뺄 수 가 없기 때문에 지정해논 num에서 배수들을 빼주는 계산을 편히 하기 위해 썼음.
에라토스테네스의 체 정리
수학에서 에라토스테네스의 체는 소수를 찾는 방법이다.
고대 그리스 수학자 에라토스테네스가 발견하였다.
알고리즘
2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
자기 자신을 제외한 2의 배수를 모두 지운다.
남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
자기 자신을 제외한 3의 배수를 모두 지운다.
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
자기 자신을 제외한 5의 배수를 모두 지운다.
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
def prime_list(n):
# 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
sieve = [True] * n
# n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True: # i가 소수인 경우
for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
sieve[j] = False
# 소수 목록 산출
return [i for i in range(2, n) if sieve[i] == True]
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges