백준 1929[소수 구하기] : 파이썬 & 시간초과 해결방법 & 소수 판정, 에라토스테네스의 체

📎 Problem

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

---

📎 Submission Code

알고리즘 문제를 풀 때, 1가지 방식으로만 접근하기보다는 다양한 방법으로 접근하는 습관을 가지자👊🏻

# case 1
'''에라토스테네스의 체 활용하기 : 시간을 줄이기 위해서 루트한 부분까지만 for 반복문'''
import sys
M, N = map(int, sys.stdin.readline().split())
prime_num = []
for i in range(M, N+1):
    condition = True
    if i == 1 : continue
    for j in range(2, int(i**0.5) + 1):
        if i % j == 0:
            condition = False
            break
    if condition:
        prime_num.append(i)
print(*prime_num, sep='\n')


# case 2
'''에라토스테네스의 체 활용하기: 사용자정의함수 만들어서 풀이하기'''
import sys
M, N = map(int, sys.stdin.readline().split())

def check_prime(num):
    if num == 1: return False
    else:
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True

for i in range(M, N + 1):
    if check_prime(i):
        print(i)

---

📎 Solution

소수를 판별하는 문제는 작년에 백준 1978번 [소수찾기]를 통해 만난 적이 있었기에, 비슷한 방법으로 풀면 될 것이라 생각을 했다.

최초에 작성한 코드는 아래와 같다. 하지만 모든 수를 반복문을 통해 확인을 해서인지 시간 초과.

당연히 안될 것이라 생각은 했지만, 혹시나 sys를 import해서 바꿔보았지만 동일하게 시간초과. for 반복문이 문제다!

'''첫번째 풀이 - 시간초과'''
M, N = map(int, input().split())
prime_num = []
for i in range(M, N+1):
    condition = True
    if i == 1 : continue
    for j in range(2, i):
        if i % j == 0:
            condition = False
            break
    if condition:
        prime_num.append(i)
print(*prime_num, sep='\n')

'''두번째 풀이 - 혹시나해서 sys로 해봤지만, 동일하게 시간초과. for문을 고쳐야할 것 같다.'''
import sys
M, N = map(int, sys.stdin.readline().split())
prime_num = []
for i in range(M, N+1):
    condition = True
    if i == 1 : continue
    for j in range(2, i):
        if i % j == 0:
            condition = False
            break
    if condition:
        prime_num.append(i)
print(*prime_num, sep='\n')

🔍 how to overcome

시간 초과를 극복한 방법은 '에라토스테네스의 체'이다. 코드에 대한 설명을 먼저 한 뒤에 개념은 아래에서 알아보자.

'''에라토스테네스의 체 활용하기 : 시간을 줄이기 위해서 루트한 부분까지만 for 반복문'''
# case 1

# 입력 받기
import sys
M, N = map(int, sys.stdin.readline().split())
# 소수 빈 리스트 생성
prime_num = []
# M부터 N까지 for문을 회전하면서 하나씩 수가 소수인지 확인
for i in range(M, N+1):
    condition = True
    # 1은 소수가 아님
    if i == 1 : continue
    # 2이상 부터 이중 for문으로 2부터 해당 수까지 반복문을 돌려 0으로 나누어떨어지는지 확인
    # 나누어 떨어지면 소수가 아니므로 바로 break
    for j in range(2, int(i**0.5) + 1):
        if i % j == 0:
            condition = False
            break
    # 이중 for문을 다 돌고 나오면, 0으로 나누어떨어지는 수가 없다는 의미
    # 즉 condition(조건)이 True이므로 소수리스트에 추가
    if condition:
        prime_num.append(i)
# 리스트 unpacking & 구분자로 줄바꿈을 넣고 출력
print(*prime_num, sep='\n')

 

'''에라토스테네스의 체 활용하기: 사용자정의함수 만들어서 풀이하기'''
# case 2
# 위의 에라토스테네스의 체 활용하기(case1) 풀이와 동일한데, 사용자 정의함수를 만들어서 풀이했다는 것만 차이가 있다.
# 굳이 소수 리스트를 만들지않고, 바로 확인 후 출력하기때문에 세번째 풀이보다 시간이 더 적게 걸린다.

import sys
M, N = map(int, sys.stdin.readline().split())

def check_prime(num):
    if num == 1: return False
    else:
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True

for i in range(M, N + 1):
    if check_prime(i):
        print(i)

---

🥕 range에서 왜 범위를 $\sqrt{}$(루트)로 줄이는 건지

아래의 예시를 보면 각각 $n$이 $12$, $100$일 때, 전체를 다 확인하는 것이 아니라  $\sqrt{12}$, $\sqrt{100}$ 즉, $2\sqrt{3}$,  $10$ 만큼만 확인을 하면 전체 소수를 확인할 수 있다.💡

예제

 

참고로 문제를 찬찬히 읽어보면, 하단에 문제에 대한 분류가 안내되어있는데 해당 문제는 아래의 분류를 가지고 있었다.

아래의 Note에서 에라토스테네스의 체를 알아보자👀

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

---

📎 Note

🔍 에라토스테네스의 체

• 에라토스테네스의 체 위키백과
• 수학에서 에라토스테네스의 체는 소수를 찾는 방법

에라토스테네스의 체

에라토스테네스의 체

🥕 알고리즘에 활용

• 소수 판별 알고리즘의 속도를 높이는 가장 대표적인 방법
• 검증하고자 하는 수의 제곱근까지만을 검증해 소수인지 판별하여, 대량의 소수를 한번에 판별할 때 속도가 빨라 유용함

---

📎 에라토스테네스의 체를 활용하는 다른 알고리즘 문제 : 소수의 개수 구하기

'''에라토스테네스의 체 활용하기 : N까지의 소수의 개수 구하기'''
# case 1

def solution(N):
    # 음수에 대한 예외처리
    if N <= 0: raise ValueError("Not Allow Zero and Negative Number")

    # 소수 확인 테이블 : True가 N+1개 원소로 담긴 list, 0부터라서 +1을 해준다
    primenum_check = [True]*(N+1)

    # 0과 1은 소수가 아님 : 0, 1번째 리스트는 False로 바꿔준다
    primenum_check[0] = False
    primenum_check[1] = False

    # 에라토스테네스의 체
    for i in range(2, int(N**0.5)+1):
        # 먼저 False로 바꿔준 0과 1을 제외하고 확인
        if primenum_check[i] == True:
            # 배수는 다 False로 바꿔준다
            for j in range(2*i, N+1, i):
                # print("i:", i,"j:", j)
                primenum_check[j] = False

    return sum(primenum_check)

# ----------------------------------------------------------------------
# case 2 : enumerate 활용하기

def solution(N):
    pass
    if N <= 0:
        raise ValueError

    # True == 1, False == 0 : case2와 마찬가지로 True인 리스트 만들어주고 1과 0은 False로 바꿔준다
    prime_list = [1] * (N + 1)
    prime_list[0], prime_list[1] = 0, 0

    # enumerate로 번호(소수, 숫자), 원소(1 or 0)를 같이 받는다
    for prime_number, v in enumerate(prime_list):
        # print(prime_list)
        if v: # 소수이면(True(=1)이면)
            # (해당소수 + 1)부터 (마지막 수)까지 돌면서 나누어지는지 확인한다
            for i in range(prime_number + 1, N + 1):
                # print("i: ", i)
                if i % prime_number == 0: # 소수의 배수이면
                    prime_list[i] = 0 # 소수가 아니다 -> (0 == False)로 바꿔준다
    # print("prime list: ", prime_list)
    return sum(prime_list)

print(solution(10))

---

🥕 case 1에서 range(2*$i$, $N$+1, $i$) 이유에 대한 부가 설명

에르스토텔레스의 체의 법칙에 따라,

2으로 나누어지면 2의 배수인 4, 6, 8, 10, 12 등도 소수에서 제외가 되고,

3으로 나누어지면 3의 배수인 6, 9, 12, 15 등도 소수에서 제외가 된다.

해당 법칙을 그대로 적용하여 $i = 2, 3, 4, ...$ 이고, $j = 2, 3, 4, ...$의 배수 이다.

코드 중간에 print문을 넣어서 확인을 해보면 아래와 같음을 알 수 있다. (solution(10)을 넣은 예시)

$10$ 이하의 소수는 $2, 3, 5, 7$로 $4(True)$개이다

출력값

---

📎 Reference

• 위키백과 : 에라토스테네스의 체
• 첫번째 이미지 출처
• 개인 깃허브에도 ipynb 파일로 정리하고 있습니다. 👀
  • https://github.com/imdona/daily-commit/blob/main/2022/220103_baekjoon_1929_primenumber.ipynb

GitHub - imdona/daily-commit