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

시작하며...

모든 알고리즘 문제 풀이는 제가 직접 짜서 정답을 맞춘 결과만을 공유합니다.

마지막 'More Solution'은 다른 정답자들 풀이 중 생각지 못했던 부분들이나 좋게 느껴진 풀이법 몇개를 가져와서 공유하였습니다.

 

[Level 1] 소수 찾기

프로그래머스

 

문제 설명

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

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

제한 조건

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

입출력 예

입출력 예 설명

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

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

 

My Solution

def solution(n):
    answer = 0
    for i in range(2, n+1):
        sqrt_n = int(i ** 0.5)
        is_prime = True
        for j in range(2, sqrt_n+1):
            if i % j == 0:
                is_prime = False
                break
        if is_prime:
            answer += 1
    return answer

• 주어진 정수 n까지의 자연수(1 제외) 중에서 소수의 개수를 찾는 문제이다. 
• 문제 풀이법을 찾다보니 소수를 구하는 방법 중에 '에라토스테네스의 체' 라는 방법이 있었는데, 구현하지 못해서 다른 정답자의 풀이를 아래에서 가져와보았다.
• 나는 직접 하나씩 다 비교해가면서 풀이를 하였다. 전체를 비교하다보니 시간 효율을 개선하는 것이 가장 큰 과제였다.
• 2부터 주어진 정수 n까지 전체 수를 비교를 한다. 확인하려는 숫자(i) 가 나누어 떨어지는 숫자가 있다면 소수가 아니라는 의미이므로 제외시킨다.
• 이때 나누어 떨어지는지 확인하는 숫자는 해당 숫자 i 의 제곱근까지만 판단(sqrt_n)을 하도록 하면 시간이 줄어들게 된다.
• 소수인지 판단하는 is_prime이라는 변수는 True 로 초기화를 해두고, sqrt_n 까지의 숫자를 다 비교해서 나누었을때 나머지가 0이면 is_prime을 False로 바꿔준다.
  • 처음에는 break를 넣지 않고 sqrt_n 끝까지 다 검사를 해주니까 효율성 테스트에서 실패를 했었다.
  • 나누어떨어지는 수가 하나라도 발견되면 그 수는 소수가 아니기 때문에 break를 넣어서 해당 루프를 바로 종료시켜주는 코드를 추가하니 효율성 테스트를 통과할 수 있었다.
• 그리고 모두 검사를 할때까지 is_prime이 True인 상태로 있다면 그 수는 소수라는 의미이므로 정답 answer에 1을 더해준다.
• 소수인 수를 의미하는 answer를 반환하면 끝!

 

More Solution

# 에라토스테네스의 체
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)

• 에라토스테네스의 체를 활용한 풀이이다. 
• 2가 소수라면 전체 숫자중에서 2의 배수를 모두 지운다. 3이 소수라면 전체 숫자 중에서 3의 배수를 지운다. 남아있는 숫자 중에서 가장 작은 숫자의 배수를 계속 반복해 나가면서 지워가는 것이 `에라토스테네스의 체`의 개념이다.
• 코드로는 집합(set) 과 차집합의 개념을 활용하여 구현한 풀이법이었다.