[프로그래머스] 소수 찾기 [연습문제] [python]

[프로그래머스] 소수 찾기 [연습문제] [python] Level1

 

문제 설명

 

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

 

입출력 예 설명

 

입출력 예 #1

1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

설계 및 구현

 

첫번째 시도

def isprime(n):
    if n < 2:
        return False
    for i in range(2, n//2+1):
        if n % i == 0:
            return False
    return True

def solution(n):
    cnt = 0
    for i in range(1,n + 1):
        if isprime(i):
            cnt += 1
    return cnt

소수 판별 함수에서 for 문을 n까지 돌려버리면 시간 초과가 날거 같아서 n//2까지 돌려 보았는데 이것도 시간초과에 걸리는 코드였다...

 

my_solutions

def isprime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def solution(n):
    cnt = 0
    for i in range(1,n + 1):
        if isprime(i):
            cnt += 1
    return cnt

두번째 시도는 n의 제곱근 까지 for문을 돌리는 코드였다.

이런식으로 코드를 짜니 시간복잡도를 통과했다.

 

모범 solution

 

def solution(n):
    answer = set(range(2,n+1))
    
    for i in range(2,n+1):
        if i in answer:
            answer -= set(range(i*2,n+1,i))
    return len(answer)

에라스토테네스의 체를 이용한 방법이다.

1. answer 에 set()자료형으로 2~n까지의 정수를 저장한다.

2. 2 ~ n까지 for 문을 돌리며 answer에 i 가 있다면 n까지의 수 중 i의 배수를 모두 제거한다.

3. answer에는 2~n까지의 소수만 남아있게 된다.

4. len(answer)을 반환하면 해결!

 

my_solutions vs 모범 solution

효율성 테스트에서 거의 10배가량의 차이가 나타난다.

생각보다 큰 차이가 나서 놀랐다.

 

***에라스토테네스의 체***