[프로그래머스][PYTHON] Lv. 1 소수 찾기

문제 설명

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

프로그래머스

 

1부터 입력받은 숫자 사이의 소수의 개수를 찾는 문제이다. 

 

첫 번째 풀이 (오답)

def solution(n):
    answer = 0
    # 1은 소수가 아니기 때문에 2부터 순회하며 소수인 수를 찾음
    for i in range(2, n+1):
        # 소수는 1과 자신으로만 나누어지는 수이므로, 
        # 2 ~ (자기자신-1) 까지의 숫자 중 나누어지는 수가 있으면 소수가 아님
        for j in range(2, i):
            if (i / j) == int(i / j):    
                break
        
        # 소수면 answer + 1
        else:
            answer += 1

    return answer

 

처음에 내가 푼 풀이는 위와 같다. 

1. 입력받은 숫자까지 존재하는 숫자를 순회한다. 이 때, 어차피 1은 소수가 아니기 때문에 제외한다. 

2. 소수는 약수가 1과 자기 자신인 수이다. 따라서 1을 제외하고는 나누어지는 수가 있으면 안된다! 
   따라서, 2부터 n-1 중 나누어지는 수가 있으면, 

   해당 숫자는 소수가 아니므로, break를 한다. 

3. 만약, 정상적으로 loop를 끝내서 나누어지는 수를 찾지 못했다면, 소수이므로 answer에 1을 더한다. 

 

 

위와 같이 풀어보면..

1~9번 테스트까지는 정답이지만, 10, 11, 12번에서는

위와 같이 시간초과가 났다 ㅠㅠ 

나름 순회를 짧게하기 위해 최대한 최적화해봤는데도

시간초과가 나서 혼란스러웠다. 

 

두 번째 풀이 (오답)

어디를 바꿔볼지 고민하다가, 구글링을 활용해 코드를 조금 수정해보았다. 

숫자 n이 소수인지 판별하기 위해서는 2부터 n-1까지의 숫자를 나누어보아야 하지만,

이는 비효율적이다. 

 

예를 들어, n이 소수가 아니라면 그 수는 반드시 두 개의 작은 약수를 가지고 있을 것이다. 

그렇다면 그 두 개의 약수 중 적어도 하나는 n의 제곱근보다 작거나 같을 것이다!

예를 들어 n이 16이라면, 약수는 1, 2, 4, 8, 16이다. 

이 때, 16의 제곱근은 4이며, 약수 중 하나는 항상 제곱근인 4보다 작게 된다. 

 

따라서, 소수를 판별할 때는 2부터 n의 제곱근까지만 확인해도 충분하다! 

제곱근보다 큰 수로 나누어봤자 이미 앞서서 확인한 작은 수로도 나누어떨어지지 않기 때문이다!!

 

# 수정 전
for j in range(2, i):
    if (i / j) == int(i / j):    
        break
        
# 수정 후
for j in range(2, (int(i**(0.5)) + 1)):
    if (i / j) == int(i / j):
        break

 

위의 논리를 바탕으로 위와 같이 수정해보았다. 

 

전체적인 코드는 아래와 같다. 

def solution(n):
    answer = 0
    # 1은 소수가 아니기 때문에 2부터 순회하며 소수인 수를 찾음
    for i in range(2, n+1):
        # 소수는 1과 자신으로만 나누어지는 수이므로, 
        # 2 ~ (자기자신-1) 까지의 숫자 중 나누어지는 수가 있으면 소수가 아님
        for j in range(2, (int(i**(0.5)) + 1)):
            if (i / j) == int(i / j):
                break
        # 소수면 answer + 1
        else:
            answer += 1
    return answer

 

그러나 이 역시 시간 초과가 나왔다ㅠㅠ

그래도 10, 12번에서는 시간초과가 나오지 않았다. 

 

좀 만 더 해보면 성공할 수 있을 것 같아서 다시 방법을 찾아보았다. 

 

세 번째 풀이 (정답)

if (i / j) == int(i / j):

 

처음에 나누어지는 수를 찾기 위해 사용한 코드는 위와 같다. 

이는 i가 j로 나눈 결과가 정수인지 확인하는 것이다. 

이 떄, / 연산자는 부동소수점 나눗셈을 수행하며, 

그 결과를 int()를 사용해 정수로 변환하여 비교한다. 

 

GPT에게 물어본 결과,, 

부동소수점 나눗셈은 정수 나눗셈보다 더 복잡한 연산이며, 이를 정수로 변환하는 과정에서도 추가적인 연산이 필요하다. 

즉, 큰 숫자를 처리할 때 연산 시간이 증가하며 추가적인 계산을 해야하기 때문에

위는 비효율적인 코드이다. 

 

따라서, 아래와 같이 바꾸어보았다. 

if i % j == 0:

 

이는 i가 j로 나누어 떨어지는지 확인한다. 

i가 j로 나누어 떨어지면 나머지가 0이 되는 특징을 이용한 것이다. 

 

 

전체적인 코드는 아래와 같다. 

def solution(n):
    answer = 0
    # 1은 소수가 아니기 때문에 2부터 순회하며 소수인 수를 찾음
    for i in range(2, n+1):
        # 소수는 1과 자신으로만 나누어지는 수이므로, 
        # 2 ~ (자기자신-1) 까지의 숫자 중 나누어지는 수가 있으면 소수가 아님
        for j in range(2, (int(i**(0.5)) + 1)):
            if i % j == 0:    
                break
        # 소수면 answer + 1
        else:
            answer += 1
    return answer

 

다행히 위의 코드에서는 100점이 나왔다ㅎㅎ

 

 

다른 사람 풀이

원래 이 문제는 '에라토스테네스의 체'를 사용해야만 풀 수 있는 문제라고 한다. 

대체 그게 뭘까,,,? 이름이 너무 어려워서 크게 와닿지는 않았다. 

 

에라토스테네스의 체는 int(n**0.5)+1 까지의 수들의 배수들을 지워가며 소수를 구해내는 방법이라고 한다. 

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)

 

우선, num에 2부터 n+1까지의 range인 set을 저장해준다. 

만약, i가 num에 있을 경우, i보다 한 배수 큰 숫자부터 n+1 까지의 범위를 공차가 i가 되게끔하여 set을 구성한 후, 

num에서 빼준다. 

 

말로하면 조금 어렵지만,,,

예시를 들어보자. 

n = 10이면, num = {2, 3, 4, 5, 6, 7, 8, 9, 10}이 된다. 

 

첫 번째로 i = 2이면, 

2는 num에 있으므로 2의 배수들을 제거한다. 

이 후, num에는 {2, 3, 5, 7, 9}가 남는다. 

 

두 번째로 i = 3이면, 

3은 num에 있으므로, 3의 배수들을 제거한다. 

이 후, num에는 {2, 3, 5, 7}이 남는다. 

 

세 번째로 i = 4면, 

4는 num에 없으므로 아무 작업도 하지 않는다. 

 

i = 5면

5는 num에 있으므로 5의 배수들을 제거한다. 

num에는 {2, 3, 5, 7} 남는다. (변경 없음)

 

i = 6이면, 

6은 num에 없으므로 아무 작업도 하지 않는다. 

 

i = 7이면, 

7은 num에 있으므로, 7의 배수들을 제거한다. 

num에는 {2, 3, 5, 7} 이 남는다. (변경 없음)

 

i = 8, 9, 10은 이미 num에 존재하지 않으므로, 아무 작업도 하지 않게된다. 

 

최종적으로 num = {2, 3, 5, 7}이며, 이 개수인 4를 정답으로 반환한다. 

 

 

느낀점

소수를 구하는 새로운 방법들을 알게 되어서 좋았다. 

잘 기억하고 써먹고 싶다.