[프로그래머스] 소수 찾기 Python Code

 

 

프로그래머스 소수 찾기 레벨 1 문제를 Python으로 보겠다.

기존에 소수 관련 문제들을 많이 올렸지만

효율성 테스트가 없었어서 아쉬웠었는데 드디어 나왔다.

---

문제

---

구현

2022.08.23 - [Coding Test/Python] - [프로그래머스] 나머지가 1이 되는 수 찾기 Python Code

2022.08.04 - [Coding Test/Python] - [프로그래머스] 소수 만들기 Python Code

이전에 올린 소수 관련 글들이다

 

이것들과 같이 sqrt를 써서 구현을 했다.

---

코드

import math

def solution(n):
    answer = 0
    for i in range(2,n+1):
        for j in range(2,int(math.sqrt(i))+1):
            if(i%j==0):
                break
        else:
            answer+=1
    return answer

2부터 n까지 탐색하고

소수 판별도 2부터 루트 n까지 반복하며 찾도록 구현했다.

---

다른 풀이

에라토스테네스의 체를 써서 구현한 사람이 있다.

이 방식은 다음과 같다.

 

2부터 n까지의 수를 모두 나열한다.

2는 소수니까 넣고 2의 배수를 모두 지운다.

3은 소수니까 넣고 3의 배수를 모두 지운다.

4는 이미 지워져 있다.

이렇게 n까지 진행하는 방식이다.

 

이것을 set의 차집합으로 구현한 코드를 보겠다.

 

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)

깔끔하고 위의 제곱근 방식보다

효율성 테스트에서 5배 이상 빠른 것으로 보인다.