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

🔒 문제

• 소수 찾기

문제 설명

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

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

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

입출력 예 설명

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

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

 

---

🔓 풀이

---

🔑 문제 해결 / 코드

def solution(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n      
    sieve[0] = False               
    # n의 최대 약수가 sprt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)             
    for i in range(2, m+1):        
        if sieve[i-1] == True:   
            for j in range(i+i, n+1, i): 
                sieve[j-1] = False
    return sieve.count(True)

---

💉 피드백

소수를 구하는 방법은 크게 4가지가 있다.

1. 2부터 판별하려는 자연수 n 전까지 나눠서 확인하는 방법
2. 2부터 판별하려는 자연수 n의 절반까지만 나눠서 확인하는 방법
3. 2부터 판별하려는 자연수 n의 제곱근 까지만 나눠서 확인하는 방법
4. 에라토스테네스의 체(대량의 소수 판별 방법)

하나의 수가 소수인지 아닌지 판별하기에는 3번 방법이 효율이 좋고, 특정 범위에서 소수의 개수가 몇 개인지 판단하기에는 4번 방법이 효율이 좋다.

 

에라토스테네스의 체 방법의 시간 복잡도를 구해보려고 했는데 수학적 공부가 부족한지 정확하게 계산은 하지 못하겠다.

검색으로 알아본 시간 복잡도는 O(Nlog logN)이다.

 

sqrt N만큼 반복하는 경우 시간 복잡도를 O(logN)으로 표기하는거 같은데 내 코드에서 최상단 루프는 n의 제곱근만큼 반복하므로 log N이 되는 거 같고 하위 루프는 if 조건을 만족할 때만 반복하고, 반복 횟수는 n까지 i의 배수가 존재하는 만큼인데 이 부분이 N log 가 돼서 O(Nlog logN)이 되는 게 아닌가 추측해본다