[Coding test][실버II]BOJ #1929 소수 구하기(수학, 정수론, 소수판정, 에라토스테네스의 체)

첫 번째 시도는 에라토스테네스의 체가 뭔지 모르고,
두 번째 시도는 알고도 틀렸다.😭 (문송…)

내 풀이

import sys
m, n = map(int, sys.stdin.readline().split())

#일반적인 소수검증하기.
def isprime(a):
    if a == 1:
        return False   #1인경우, 소수판정 제외한다.
    
    else:
        #2부터 입력 a의 제곱근까지의 수들 중에서 2부터 i에 할당한다.
        for i in range(2, int(a**(1/2)) + 1): 

            #만약 i로 나눠떨어진다면, 1을 제외한 수들 중 약수가 있다는 의미이므로 소수가 아니다.
            if a % i == 0:
                return False 
    
        #만약 소수이면 True를 리턴한다.
        return True 
    


for i in range(m,n+1):
    if isprime(i):
        print(i)

문제 정의

💡 에라토스테네스의 체

에라토스테네스의 체란 수학자 에라토스테네스가 만들어낸 소수를 찾는 방법으로,

마치 체로 치듯이 수를 걸러낸다고 해서 에라토스테네스의 체라고 부른다.

💡 소수를 판정하는 방법

만약 9를 소수 판정한다고 하자.  

소수란 자기자신과 1을 제외한 수로 약분되지 않는 수를 의미한다. 

다르게 말하면 1과 자기자신을 제외한 수로 나눠진다면 그 수는 소수가 아니다.

그리고 모든 수는 (a*b) 로 나타낼 수 있는데, 
제곱수는 홀수의 쌍을 갖고, /9는 (1,9), (3,3), (9,1)
제곱수가 아니라면 짝수의 쌍을 가진다. /10은 (1,10), (2,5), (5,2), (10,1)
제곱수는 (k,k)의 쌍을 하나 더 가지기 때문에 홀수의 쌍을 갖게된다.

제곱수를 생각해보면  (k,k)를 기준으로 좌 우측에 원소의 위치만 다른 쌍들을 가지게 된다.
즉, √n 을 기준으로 좌우측에 쌍들을 가질 수 있다.

좌측 쌍에 대해 체크하면 자동으로 우측쌍도 체크하게되므로, 좌측쌍만 체크하면 된다.
좌측 쌍에 대해서, a의 범위는 1이상 √n 미만이다.

소수의 경우, 이 범위 내에서 1만 가질 수 있으므로, 다르게 말하면 
2이상 √n 사이에 값으로 n이 나눠지지 않는다면 그 수는 소수이다.

이 방법은 각각의 수에 대해 판정을 할때 사용가능하다. 그리고 N의 제곱근에 대해서 루프가 돌아가기때문에 시간복잡도가 O(sqrt(n))이다.

이런 소수판정 방법에는 문제가 있는데,
N개의 수에 대해서 각각 소수판정을 하고 싶을때는 N개의 수에 대해 각각 소수판정을 해야하므로
시간복잡도가 O(N)으로 높아진다는 것이다.

💡 에라토스테네스의 체 사용방법

‘범위’에 대한 소수판정 시, 유용하게 쓰이는 것이 에라토스테네스의 체이다.
N개 이하의 소수를 찾고 싶을때, 2<= x <= √N 인 x에 대해
‘자기자신을 제외한 배수’를 모두 빼주면 소수만 남는다.

에라토스테네스의 체의 시간복잡도는 O(n(log(log n)) 이다.
시간복잡도 O(1)에 가깝다는 것만 알아두도록 하자.

✏️ 에라토스테네스의 체 코드

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

에라토스테네스 활용한 문제풀이

def prime_list(m,n):
    # 에라토스테네스의 체 초기화: n+1개 요소에 True 설정(소수로 간주),인덱스넘버=숫자
    sieve = [True] * (n+1)  

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    checkerrange = int((n+1) ** 0.5)
    for i in range(2, checkerrange + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n+1, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False
    sieve[0] = False
    sieve[1] = False

    # 소수 목록 반환
    return sieve


import sys

m,n = map(int, sys.stdin.readline().split())

sieve_list = prime_list(m,n)
for index, value in enumerate(sieve_list):
    if index >= m and value == True:
        print(index)