소수 찾기 / 프로그래머스, 파이썬 코딩테스트 연습 연습문제

문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.(1은 소수가 아닙니다.)

 

 

제출답안

 

def solution(n):
    def is_primeN(n):
        """
        소수 탐지 함수
        @param n: int
        return 0 or 1
        """
        output = 1 # 기본값(True)
        for num in range(2, int(n**0.5)+1):
            # 1과 주어준 수의 제곱근 사이에 약수가 하나라도 있으면 소수가 아니다.
            if not n % num: 
                output = 0
                break
        return output
    
    # 2 이상의 홀수만 대상으로 체크 (2 이상의 짝수는 소수가 아니다)
    ls_odd = [num for num in range(2, n+1) if num%2]
    
    # 솟수 점검범위: 2, 그 이상의 홀수
    answer = 1 + sum([1 for num in ls_odd if is_primeN(num)])
    return answer

다른사람 풀이

에라토스테네스의 체라는 소수를 찾는 방법이 있었다
그리고 성능이 상상을 초월했다.

---

위키백과 [에라토스테네스의 체] 바로가기

해당 코드는 아래와 같다.

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)

 

저자의 코드 (좌) / 가장 좋아요를 많이 받은 사람의 코드 (우)

 

다른 사람의 풀이를 개선

 

위 코드에서 숫자를 확인하는 경우의 수를 줄이는 것으로 마무리지었다.
추후에, 더 개선시켜보는 것으로

아래가 최종 코드와 그 결과물이다

 

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

문제 바로가기