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

 

 

시간 초과

def solution(n):
    answer = 0
    # 약수가 1,n을 제외하고 없다면 소수
    for i in range(2,n+1) :
        for j in range(2, i) :
            if i % j == 0 :
                break
            elif j==i-1 :
                answer += 1
    if i >= 2 : answer += 1
    return answer

가장 간단한 방법으로 구현하였다.

이중 for문으로 주어진 숫자 n에 대해서

2~n-1 까지 나눠지는 숫자가 있다면 소수가 아닌것으로 판별하였는데,

시간 초과로 실패하였다.

이는 숫자가 매우 커진다면 아주 비효율적이기 때문이다.

 

 

 

통과한 풀이

약수의 특징을 이용한 풀이이다.

약수는 항상 짝을 이루기 때문에, 약수를 구하려면 해당 숫자의 제곱근(루트) 까지만 나눠지는지 확인하면 된다.

즉, 약수의 중간값을 기준으로 한 쪽만 검사를 하더라도 다른 쪽의 약수들을 알 수 있다.

예로 8의 약수는 1,2,4,8이다.

1x8 = 8

2x4 = 8 로 약수끼리 짝을 맞춰 곱한 수가 8이기 때문에,

8의 제곱근인 2.xx, 즉 int(8**0.5) = 2까지만 8에서 나눠보면 된다.

이때 8은 2로 나눠지기 때문에 소수가 아님이 증명된다.

 

또 다른 예로 45의 약수는 1,3,5,9,15,45이다.

이 또한 각 짝수끼리 짝이 맞춰지므로, 45의 제곱근인 6.xx , 즉 6까지만 나눠지는지 확인해보면된다.

이때 45는 3으로 나눠지므로 소수가 아님이 증명된다.

 

이러한 특징을 이용하여 에라토스테네스의 체 알고리즘 으로 문제를 풀 것이다.

작동 방법은 다음과 같다.

 

1. 2 ~ N까지의 범위가 담긴 배열을 만든다.

 

2. 해당 배열 내의 가장 작은 수 i 부터 시작하여, i의 배수들을 해당 배열에서 지워준다. (i는 소수이기 때문에 i 자기자신은 지우지 않는다.)

 

3. 주어진 범위 내에서 i의 배수가 모두 지워지면 i 다음으로 작은 수의 배수를 같은 방식으로 배열에서 지워준다.

 

4. 더 이상 반복할 수 없을 때까지 2, 3번의 과정을 반복해준다.

 

* 이때 아까 말했던 약수의 특징을 이용하면, N까지 반복문을 확인하지 않고 N의 제곱근까지만 확인을 하여도 될 것이다.

왜냐하면 1~100까지의 소수를 구하는 문제가 주어졌을 때, 100의 경우 10 이하에서 이미 소수가 아님이 판별이 되었을 것이고,

97의 경우 제곱근이 9.xx 로 2~9까지의 숫자의 배수라면 이미 지워졌을 것인데, 지워지지 않았으므로 소수임이 증명된다!

def solution(n):
    answer = 0
    prime = [True for _ in range(n+1)] # 소수를 True라고 표기한 배열
    
    for i in range(2,int(n**0.5)+1) :
        j = 2
        while i*j <= n :
            prime[i*j] = False
            j+=1
    
    for i in prime[2:] :
        if i : answer += 1
        
    return answer

prime -> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  
i = 2~4까지 반복문
1) i = 2 일때

• j = 2 -> 4
• j = 3 -> 6
• ...
• j = 10 -> 20
• prime -> 1 3 5 7 9 11 13 15 17 19 

2) i= 3 일 때

• i=3
• j=2->6
• j=3->9
• j=4->12
• j=5->15
• j=6 -> 18
• prime -> 1 3 5 7 11 13 17 19

3) i=4 일 때

• i=4
• j=2 -> 8
• j=3 -> 12
• j=4 -> 16
• j=5 -> 20
• prime -> 1 3 5 7 9 11 13 15 17 19

 

 

다른 풀이

def solution(n):
    prime = set(range(2,n+1))
    
    for i in range(2,int(n**0.5)+1):
        if i in prime :
            prime -= set(range(i*2,n+1, i))
            
    return len(prime)

더 빠른 풀이이다!!

set 을 이용하여 집합끼리의 차집합으로 더욱 빠른 연산이 가능하다.

s-t 를 할 때의 시간복잡도는 O(len(s) + len(t)) 이기 때문이다!

 

먼저 prime 배열을 2~n까지로 초기화하고, 2부터 n의 제곱근까지 돌면서

만약 prime 안에 있는 숫자라면, 해당 숫자의 배수 집합을 prime 에서 모두 제거하는 연산을 수행한다.

prime안에 없다면? 이미 지워진 숫자이므로 해당 연산이 필요없다!