문제 보기
더보기
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
- n은 2이상 1000000이하의 자연수입니다.
입출력 예
n result10 | 4 |
5 | 3 |
입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
<나의 풀이> - 시간 초과
def sosu(num):
cnt = 0
for i in range(1, num):
if num % i == 0:
cnt += 1
if cnt == 1:
return True
def solution(n):
answer = 0
for i in range(2, n+1):
if sosu(i) == True:
answer += 1
return answer
*에라토스테네스의 체 알고리즘 이용
에라토스테네스가 고안한 소수(素數)를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.
2부터 n까지의 숫자중에서 에라토스테네스의 체로 소수를 찾으려면, 2부터 시작해 n까지의 자연수를 차례로 쓴다. (2, 3, 4, ..., n)
그리고 2 이외의 2의 배수를 지운다(p=2). 이때 2가 최초의 소수가 된다.
그 다음 소수인 3을 제외한 3의 배수를 지운다(p=3).
이 방법을 다음에 지울 소수, 즉 p의 제곱이 n 보다 커질 때까지, 이 방법을 계속한다(p2≥n).

[네이버 지식백과] 에라토스테네스의 체 [Eratosthenes' sieve] (두산백과 두피디아, 두산백과)
<정답>
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)
'[프로그래머스] > python' 카테고리의 다른 글
[프로그래머스] Lv2. 최댓값과 최솟값 (0) | 2024.03.05 |
---|---|
[프로그래머스] 과일장수 (0) | 2024.03.03 |
[프로그래머스] 코딩테스트연습>코딩테스트입문>옹알이(1) (2) | 2024.02.25 |
[프로그래머스] 코딩테스트 연습>연습문제>이상한 문자 만들기 (0) | 2024.02.17 |
[프로그래머스] 코딩테스트 연습>연습문제>달리기 경주 (2) | 2024.02.14 |