소수 찾기

문제 설명

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

 

풀이

def solution(n):
    answer = 0
    for i in range(2,n+1):
        cnt = 0
        for j in range(1,i//2+1):  # 수의 절반까지 조사하고 약수 존재를 알아낸다
            if i % j == 0:
                cnt += 1

            if cnt >= 2:
                break
        if cnt == 1:
            answer += 1

    return answer

역시나 어림도 없다. 이중 for 구문이 나오면 시간초과를 할 때가 많다.

n 이하의 모든 수를 소수인지 판단하는 과정에서 이미 소수로 밝혀지면 그것만 사용하면 된다.

 

밝혀진 소수를 새로운 배열을 만들어서 추가하는 것보다 합성수를 기존 배열에서 뺴주는 게 나을 것 같다.

def detector(n, arr):  #합성수가 제거된 arr를 갱신하여 받음
    cnt = 0
    for i in arr:
        if n >= i:        # 소수만 남긴 arr에서 n보다 작은 수만 입력 
            if n % i == 0: # arr에서 나눠 떨어지는 첫번 째 수를 반환 
                return i  # n=4라면 i=2일 것이다. // 조기 종료를 할 수 있음
                
def solution(n):
    num = list(range(2,n+1))
    for i in range(2,n+1):
        via = detector(i,num)
        if via != i:         # i=4라면 via는 2가 나올 것이기 때문에
            num.remove(i)    # 4는 합성수이므로 제거한다.
            
    return len(num)

소수를 따로 배열로 빼서 검색 수를 줄였고, 소루 검색 함수를 조기종료할 수 있는 조건을 달았지만 여전히 시간을 초과한다. 더 큰 연산량을 해결할 수 있는 방법을 찾아야한다.

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))  # i=3이라면 다음 3의 배수는 2*3이므로 시작 위치를 잘 선언했다
            
    return len(num)

다른 고수의 풀이다. 2의 배수, 3의 배수를 모조리 없애는 방법을 값 하나하나 검색하는 것이 아닌, i번씩 건너뛰면서 값을 삭제한다.

리스트 index를 조사하는 게 아니라 set의 키를 바로 제거하는 거라 참조도 빠르다.

set과 dict에 익숙해질 필요가 있을 것 같다.

 

 

출처

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스