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

isTuna·2020년 11월 25일
0

[프로그래머스]

목록 보기
3/9

문제 설명

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

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

제한 조건

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

입출력 예 설명

nresult
104
53

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

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


나의 풀이

풀이 1

처음 접근한 방식은 자신보다 작은 소수로 나누어지지 않는 수는 소수라는 특징을 살린 방식이였습니다. 단순하게 모든 수와 나누어보는 것 보다는 빠르지 않을까 하고 구현해보았습니다.

def solution(n):
    answer = 0
    DEC = [2]
    for i in range(2,n+1):
        for j in range(0,len(DEC)):
            if i%DEC[j]==0:
                break
            elif j==len(DEC)-1:
                DEC.append(i)
                #print(DEC)
    return len(DEC)

DEC이라는 소수를 담는 list를 만들어 가장 작은 소수 2를 미리 넣어놓고 다음 들어오는 수가 DEC에 있는 모든 수와 나누어봐 나머지가 없으면 DECappend()했습니다. 마지막에는 DEC의 크기가 소수의 개수이기 때문에 len(DEC)을 반환했습니다.

이렇게 만들어진 코드는 16개의 테스트 중 9개만 통과하고 나머지는 시간초과로 실패하였습니다. 그래서 새로운 방식으로 접근했습니다.


풀이 2

소수를 찾는 방식 중에 에라토스테네스의 체라는 방식이 있습니다. 고대 수학자 에라토스테네스가 발견한 방식으로 2의 배수부터 제거하고 그 후에 제거되지않은 수는 소수이며 해당 소수의 배수를 다시 제거합니다. 이렇게 찾는게 아닌 역으로 지우는 방식으로, 아래 gif를 보면 이해가 잘 될 것입니다.

def solution(n):
    answer = 0
    DEC = [True] * (n+1)
    for i in range(2,n+1):
        if DEC[i]==True : 
            for j in range(i,n+1,i):
                DEC[j]=False
            answer += 1
        else:
            continue

    return answer

이를 코드로 구현한 모습입니다. 저는 먼저 입력된 정수 n만큼 DECTrue를 정의해주었습니다. 그 다음에 2부터 n+1까지 수 중에 True인 값이 있으면 그 값의 배수를 모두 False로 바꾸어주었습니다.

이 방식을 통해 남은 수는 모두 소수 이므로 True가 발견 될때마다 answer를 1씩 증가시켰습니다.


후기

에라토스테네스의 체를 전에도 사용한 기억이 있어서 해결할 수 있었지만 해당 알고리즘에 대한 지식이 없었으면 효율성 테스트에서 고생했을 것 같다.

profile
청소연구소 개발자 (2021. 05~ )

0개의 댓글