🧬[아리스토테네스의 체]의 소수판별 알고리즘

<소수 판별 알고리즘을 접하기 전의 문제인식과 풀이>

시간 복잡도를 생각하지 않고 풀던 브론즈 난이도에서는 배열을 생성하고 이중 반복문으로 문제를 많이 해결했다.
하지만 Silver 난이도로 올라오면서 슬슬 시간 초과가 발생하는 경우가 빈번히 발생하기 시작하였고,
이에 시간복잡도를 공부하게 되었다.

 

시간 복잡도를 공부하며 배운 내용을 통해 본다면...

배열의 갯수가 n 개이고 이 배열을 이중으로 완전 탐색한다면 시간 복잡도는 O(N^2) 이 된다.
1초에 1억번 연산할 수 있다는 제한사항이 주어진다면, 배열의 최대 길이는 10^8 (1억)의 제곱근 이므로
제한시간 1초에 해결할 수 있는 배열의 길이는 10^4, 즉 10,000 이다. 

 

배열의 최대길이가 10,000 이 넘는다면 완전탐색을 위한 이중반복문은 시간초과로 실패이다!!!!!!!!!(1초 제한일 경우)

참고로 2초의 경우 2억의 제곱근 만큼 배열의 갯수를 완전탐색 가능하다는 계산이 나오기 때문에, 약 14,000의 배열의 길이를 이중 완전탐색 할 수 있다.(정확히 14,142)

 

그렇다면, 주어진 자료로 배열의 길이가 10,000이 넘어간다면
O(n) 의 시간복잡도를 갖는 알고리즘을 써야하고, 더 나아가 O(log n)의 시간 복잡도를 같는 알고리즘을 선택해야 문제를 풀 수 있다.

 

위의 백준 1929 문제 역시, 이중 반복문으로 배열의 완전탐색 알고리즘으로 접근했고, 문제에서 최대 1,000,000 이하의 수가 주어진다.
최악의 경우 배열의 길이 1,000,000 을 모두 탐색한다면 내가 만든 알고리즘에서 시간복잡도는 10의 6승의 제곱이므로 10의 12승이 되고, 1초에 1억번 연산 가능한 컴퓨터에서는 10의12승 / 1억  = 10,000 즉, 10,000초가 걸린다는 계산이 나온다...(2시간 46분 40초)

 

아래는 시간초과로 실패한 이중탐색 알고리즘이다.

firstNum,secondNum = map(int,input().split())

stack = []
sosu = []
for i in range(1,secondNum+1):
    stack.append(i)
for i in range(1,secondNum+1):
    count = []
    for j in stack:
        if i % j == 0:
            count.append(j)
        elif j > i:
            break
        elif len(count) > 2:
            break
    if len(count) == 2:
        sosu.append(i)
for i in sosu:
    if firstNum <= i <= secondNum:
        print(i)

 

자기 자신과 1로만 나누어 떨어지는 수인 소수는 영어로 Prime Number 인데, 잘 몰라서 일단 변수명으로 sosu 를 썼다...

elif 문을 이용해 자기 자신보다 큰 수로 나누는 경우, 또 나누어 떨어지는 수가 2이상인 경우에 반복문을 탈출하고자 했지만 시간복잡도를 줄이기에는 역부족이였다!

 

<아리스토테네스의 체 : 소수판별 알고리즘>

 

아리스토테네스

이 할아버지가 아리스토테네스 이고, 직업은 수학자 라고 나온다. 고대 그리스의 수학자인데, 아무튼 이 할아버지가 고안해서 만들어내신 소수판별 알고리즘을 알아보자면

 

1. 핵심개념

• 주어진 모든 범위의 모든 수를 소수라고 가정하고, 이를 위해 True 값을 가진 boolean 배열을 사용한다.
• 가장 작은 소수부터 시작하여, 그 소수의 배수를 소수가 아닌것으로 바꾼다.
• 다음 소수를 찾기 위해 배열의 탐색을 제곱근 까지 반복한다.
• 배열에 True 로 남아있는 인덱스가 소수이다.

2. 작동 방식

• 1부터 30까지의 수 중에 소수를 찾는다고 가정하면
• 2부터 30까지 인덱스가 Ture 인 boolean 배열을 만든다. (0과 1은 소수가 아니기 때문에 제외하고 시작)
• 2부터, 2의 배수가 있는 인덱스의 값을 False 로 바꾼다
• 3부터, 3의 배수가 있는 인덱스의 값을 False 로 바꾼다.
• 다음에 남아있는 소수는 5 이므로 ( 4는 2의 배수에서 False 로 바뀜), 5의 배수가 있는 인덱스 값을 False 로 바꾼다.
• 이 과정을 반복하여 주어진 범위까지의 소수를 찾는다.

3.시간복잡도

• 각 수의 배수가 있는 만큼 총 배열의 길이가 계속해서 줄어들기 때문에 O(log n) 이다.

4. 구현

def primeNumber(n):
    # 0과 1은 소수가 아니므로, n+1 크기의 배열을 생성
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0과 1은 소수가 아님

    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:  # i가 소수인 경우
            # i의 배수를 False로 표시
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    # 소수 목록 생성
    primes = [i for i, prime in enumerate(is_prime) if prime]
    return primes

# 사용 예시
n = 30
print(f"{n} 이하의 소수: {primeNumber(n)}")

 

이제 이 지식은 제 겁니다.  제 마음대로 구현 할 수 있는 것입니다.

 

 

 

아리스토테네스의 방법으로 구현한 코드는

firstNum,secondNum = map(int,input().split())
printNumber = []
for i in range(secondNum+1):
    printNumber.append(i)

is_sosu = [True]*(secondNum+1)
is_sosu[0] = is_sosu[1] = False

for i in range(2,secondNum+1):
    if is_sosu[i]:
        for j in range(i*i,secondNum+1,i):
            is_sosu[j] = False

for i in printNumber:
    if is_sosu[i] == True:
        if firstNum <= printNumber[i] <= secondNum:
            print(printNumber[i])

 

풀이

1. 주어진 수 가 10 이라면, 0부터 10까지 배열에 수를 채워서 출력용 자료구조를 하나 만듬. (변수 printNumber ~ 첫번 째 반복문)
2. is_sosu 배열에 0부터 10까지 (길이 11) True 인 배열을 만들고, 0과 1은 False 로 만든다 (소수 아님)
3. i=2부터(10까지 가려면 11로) 시작하는데, 만약 i 의 값이 True 라면 2부터 10까지 2의 배수의 값들을 False 로 변경
4. i = 3 이라면, is_sosu[3] 이 True 인지 판단하고 맞다면 -> 3부터 10까지 3의 배수들의 값을 False 로 변경
5. 이렇게 이중반복문을 다돌고나면 1~10까지 소수의 인덱스값이 남아있는 boolean 배열이 남아있게 된다.
   is_sosu = [False,False,True,True,False,True,False,True,False,False,False]
6. 그냥 반복문으로 True의 인덱스 값을 출력하려 했더니 2번 인덱스가 계속 출력이 된다. 그래서 pirntNumber 를 1대 1로 대응 시켜서
   is_sosu[i] == Ture ->  printNumber[i] 즉 is_sosu[2] == True -> printNumber[2] 가 출력되도록 했다.
7. 백준 1929번 문제에서는 처음 주어진 수 부터 다음에 주어진 수 사이의 소수들을 출력하라고 했으므로, printNumber[i] 값이 첫번째 수보다 크거나 같으면 출력하기 시작하도록 조건문을 설정했다.

* 전체 탐색의 배열의 길이(=주어진 수)를 제곱근으로 하라고 했는데, 즉 10이면 3.xxxxx일 테니, 3+1 =4 로 하라고 했는데, 잘 이해가 가지 않아 주어진 수 만큼의 배열 길이로 설정하고 했다. 하지만 다 풀고 생각해보니 일단 2가 소수가 되면서 짝수가 다 사라져버리기 때문에 전체 탐색해야 하는 배열의 길이가 줄어들어버리기 때문에, 배열의 길이의 제곱근으로 탐색해도 될 것 같다. 아리스토테네스 할아버지 의심해서 죄송해요!

결과

주어진 수 범위안에 출력하는 조건을 안붙여서 출력 초과가 한 번 났다ㅠㅠ

 

제 마음대로 구현할 수 있는 것 입니다.