데일리 알고리즘 230113

데일리 알고리즘 230113

---

프로그래머스, 소수 찾기

프로그래머스

 

계속 유효성검사, 테스트 끝에 3개에서 런타임오류...

소수찾기 검색을 해봤다.

 

📌 에라토스테네스의 체

에라토스테네스의 체(Sieve of Eratosthenes)는 소수를 구하는 효율적인 알고리즘입니다.
이 알고리즘은 2부터 n까지의 숫자를 가지고 시작하며, 2부터 시작하여 소수를 찾아나가는 과정입니다.

과정은 다음과 같습니다.

2부터 n까지의 숫자를 가지고 소수 후보를 만듭니다.
2부터 시작하여 각 숫자를 확인합니다. 첫번째 숫자는 2이며, 2는 소수이므로 소수로 판별합니다.
2의 배수를 제외하고 남은 숫자 중 가장 작은 숫자를 찾습니다. 이 경우는 3입니다. 3도 소수이므로 소수로 판별합니다.
3의 배수를 제외하고 남은 숫자 중 가장 작은 숫자를 찾습니다. 이 경우는 5입니다. 5도 소수이므로 소수로 판별합니다.
이 과정을 반복하여 남은 숫자 중 가장 작은 숫자를 찾아 소수인지 판별!

 

n이 커질수록 소수를 구하는데 걸리는 시간이 많이 걸리게 됩니다.

이럴때, 제곱근 기반의 기법을 사용하면 알고리즘의 효율을 향상 시킬 수 있습니다.

 

📌 100의 소수를 구해보자!

# 1 에서 10 까지만 살펴보면 됨.

1 2 4 5 10 20 25 50 100
| | | |_____|  |  |  |
| | |__________|  |  |
| |_______________|  |
|____________________|

이러한 특성으로 인해 100의 제곱근까지만 탐색하고 그 배수들을 다 없애면 소수만 남을 수 있다.

 

 

📄 나의 코드

def solution(n):
    array = [0]*(n+1)
    array[0] = array[1] = 1

    for i in range(2, int(n**0.5) + 1):
        if array[i] == 0:
            for j in range(i*i, n+1, i):
                array[j] = 1
    return array.count(0)

index가 곧 소수를 의미한다.

배열은 0부터 시작하므로 10까지 탐색하기 위해서 11자리의 배열을 생성해야 한다.

 

10 이하의 소수를 찾는다고 가정해보자

값  [0,0,0,0,0,0,0,0,0,0,0]
idx [0,1,2,3,4,5,6,7,8,9,10]

0과 1은 소수가 아니므로 1로 두고

2부터 10의 제곱근(3)까지 탐색한다.

 

2는 소수이므로 0으로두고 2의 배수를 index(4, 5, 6, 8, 10)로 가지는 배열의 값을 1로 바꾼다.

3는 소수이므로 0으로 두고 3의 배수를 index(6, 9)로 가지는 배열의 값을 1로 바꾼다.

 

이렇게 되면 2번 탐색만에 10이하의 소수를 찾을 수 있다.