[프로그래머스] LEVEL - 1 소수 찾기 [에라토스테네스의 체]

 

 

def solution(n):
    answer = 0
    prime = []
    
    for idx in range(1, n+1):
        cnt=0
        for jdx in range(1, idx+1):
            if idx % jdx ==0:
                cnt+=1
                
        if cnt==2:
            prime.append(idx)
            
    answer = len(prime)
    return answer

소수 찾기 문제를 이렇게 기존 문제 풀듯 풀었다. 

 

하지만 시간초과로 효율성 테스트와 일부 결과는 실패 

O(X) ->> O(X)보다 더 빠르게 동작할 수 있는 알고리즘을 작성해야함.

 

 

 

소수

2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수

---

 

에라토스테네스의 체 

에라토스테네스의 체 알고리즘을 사용하여 소수 찾기를 간단하게 구현할 수 있다는 것을 알았다. 

 

에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘

 

16이라는 수의 약수는

1, 2, 4, 8, 16

1*16 = 16

2*8 = 16

4*4 = 16

8*2 = 16

16*1 = 16 

가운데 약수를 기준으로 각 등식이 대칭적인 형태

 

특정한 자연수 x가 소수인지 확인하기 위해 바로 가운데 약수까지만 나누어 떨어지는 지 확인한다.

위 예시에서 4까지만 확인하면 된다. 

즉 2, 3, 4를 확인하여 나누어 떨어지는 지 확인한다.

제곱근 까지만 (가운데 약수) 확인하면 된다는 점.

 

ex 8의 약수도

1 * 8 = 8

2* 4 = 8

4 * 2 = 8

8 * 1 = 8 

이므로 1,2,4,8이다. 

8도 마찬가지로 8의 제곱근까지만 확인하면 된다. 8의 제곱근은 약 2.828이므로 2까지만 확인하면되고, 3부터는 확인할 필요가 없다.

즉, 시간 복잡도는 O(X^1/2) 에 소수 판별이 가능하다. 

 

 

import math


def is_prime_number(x):
     # 2부터 x의 제곱근까지의 모든 수를 확인하며,
    for i in range(2, int(math.sqrt(x))+1):
        # x가 해당수로 나누에 떨어진다면
        if x%i == 0:
            return False
    return True # 소수

print(is_prime_number(4))

이 산식은 코딩테스트를 준비하며 종종 소수 문제가 나오니 이정도는 외워 두는 것으로ㅜ

 

 

위 산식을 이용해 [소수찾기] 풀은 과정

import math


def is_prime_number(x):
     # 2부터 x의 제곱근까지의 모든 수를 확인하며,
    for i in range(2, int(math.sqrt(x))+1):
        # x가 해당수로 나누에 떨어진다면
        if x%i == 0:
            return False
    return True # 소수

print(is_prime_number(4))
print(is_prime_number(7))

n= 10
prime = []
for i in range(2,n+1):
    if is_prime_number(i) == True:
        #print('TRUE',i)
        prime.append(i)

print(len(prime))

1부터 10까지의 소수 판별이더라도, 1은 소수가 아니기 때문에 2부터 시작함.

 

 

엥 이렇게 했는데도 시간초과가 뜨는데..?

---

참고한 다른 풀이 ...

 

def solution(n):
    answer = 0

    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까지 num값에 set을 만들어준다. 이 num 셋에 들어있는 수들은 

 

for 문으로 확인하면 결과는 아래와 같다

알고리즘이 잘 이해가ㅏ 안가는데....