프로그래머스 | 소수 찾기 [파이썬 python]

프로그래머스

 

코드

import math
def isPrime(n):
    if n==1: # 1은 약수가 아니므로 제외
        return False
    else:
        for i in range(2,int(math.sqrt(n))+1): # n의 제곱근까지 약수가 존재하는지 확인
            if n%i==0: # 약수가 존재하면 False
                return False
        return True # 존재하지 않으면 True
    
def solution(n):
    answer = 0
    for i in range(1, n+1):
        if isPrime(i):
            answer += 1
    return answer

n이 소수인지 판별하는 isPrime 함수를 만들었다.

isPrime 함수는 n이 소수이면 True를, 소수가 아니면 False를 리턴한다.

1부터 n까지의 수를 isPrime 함수에 매개변수로 전달하여, 소수이면 answer에 +1을 하여 최종적으로 1부터 n까지의 수 중 소수의 개수를 리턴한다.

이 코드를 제출하면 모든 케이스를 통과하여 정답으로 채점되지만, n이 커질수록 오랜 시간이 소요되어 다른 사람들의 코드를 찾아보았다.

 

다른 사람의 코드 - 1) 리스트 이용

def solution(n):
    a = [False, False] + [True]*(n-1) # 0, 1 False(소수가 아니므로) / 2부터 소수라고 가정
    primes = [] # 소수
    
    for i in range(2, n+1):
        if a[i]: # 소수이면
            primes.append(i) 
            for j in range(2*i, n+1, i): # 2*i부터 n까지 i의 배수 False로 바꾸기
                a[j] = False
    return len(primes)

a는 1부터 n까지의 수가 소수인지 아닌지 T/F를 담은 배열이다.

리스트 특성상 0번 인덱스부터 시작하므로 0에는 False를 담고, 1은 소수가 아니므로 1번 인덱스에도 False를 담는다. 

그다음 2부터 n까지의 값을 소수라고 가정하고 True를 담는다.

 

이제, 2부터 n까지의 수가 소수인지 판별한다.

i가 소수이면(a[i] = True이면) 소수를 담는 리스트인 primes에 i를 추가하고, i의 배수를 모두 False로 바꾼다.

i가 소수이면 i의 배수는 모두 소수가 아니다. ex) 2는 소수, 2의 배수인 4, 6 ,8 ,10.. 은 소수가 아님

n까지 모든 반복이 끝나면 소수의 개수(=len(primes))를 리턴한다.

 

다른 사람의 코드 - 2) 집합 set 이용

def solution(n):
    num=set(range(2,n+1)) # 2부터 n까지의 집합

    for i in range(2,n+1): 
        if i in num: # i가 num에 있으면
            num-=set(range(2*i,n+1,i)) # 집합 num에서 i의 배수 제외
    return len(num)

리스트를 이용한 코드와 논리는 같지만, 집합 set을 이용한다는 점을 눈여겨볼 수 있다.

 

먼저, 2부터 n까지의 수가 담긴 집합 num을 만든다.

그다음 2부터 n까지의 수를 돌며 해당 수(=i)가 num에 있는지 확인한다.

num에 i가 존재하면 num에서 i의 배수를 모두 제거해준다.

이 과정 역시 set을 이용하여 2*i부터 n까지의 모든 i의 배수를 찾았다.

집합 간 -(빼기) 연산이 가능하기 때문에 집합 num에서 집합 i의 배수를 빼면 i의 배수가 아닌 수들이 num에 남게 된다.

n까지 모든 수를 돌고 나면 num에는 소수만 남기 때문에 len을 통해 소수의 개수를 구할 수 있다.

 

위 두 방법을 보고 처음에는 이해가 잘 되지 않았다. for문에 i를 하나씩 대입하여 과정을 살펴보면 훨씬 수월하게 이해할 수 있다.

처음엔 나도 2, 3까지는 소수니까 당연하다고 생각했지만 4는 그럼 어떻게 하지?라는 생각으로 꽉 막혀있었는데 배수를 모두 제거한다는 개념을 익히고 비슷한 다른 문제에서도 사용해 보아야겠다.