처음에 이중for문으로 해결하려다 보니 n이 클 때 시간복잡도가 크게 증가하여 시간초과로 통과하지 못했다.
힌트를 얻기 위해 질문하기에 들어가봤다. '에라토스테네스의 체' 라는 개념을 사용해야 한다.
그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수(素數)를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다. [네이버 지식백과] 에라토스테네스의 체 [Eratosthenes' sieve] (두산백과)
통과한 답 :
def solution(n):
l=[False,False]+[True]*(n-1)
primes=[]
for i in range(2,n+1):
if l[i]:
primes.append(i)
for j in range(2*i,n+1,i): #i씩 건너가면서 배수들을 삭제
l[j] = False
return len(primes)
다른 사람의 풀이 :
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)
👏🏻👏🏻👏🏻
'공부 > 코딩테스트' 카테고리의 다른 글
[프로그래머스] 최대공약수와 최소공배수, 콜라츠 추측, 핸드폰 번호 가리기 (0) | 2021.01.07 |
---|---|
[프로그래머스] 2020카카오 인턴십-키패드 누르기 (0) | 2021.01.07 |
[프로그래머스] 제일 작은 수 제거하기, 정수 제곱근 판별 (0) | 2021.01.06 |
[프로그래머스] 자연수 뒤집어 배열로 만들기, 정수 내림차순으로 배치하기 (0) | 2021.01.05 |
[프로그래머스] 자릿수 더하기, 이상한 문자 만들기 (0) | 2021.01.01 |