[99클럽 코테 스터디 1일차 TIL] 소수 구하기

 

오늘의 학습 키워드

소수 구하기

공부한 내용 본인의 언어로 정리하기

문제

백준 1929 - 소수 구하기

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

코드

m,n = map(int, input().split())
for i in range(m, n+1):
    if i == 1:
        continue
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0:
            break
    else:
        print(i)

 

해당 문제는 m, n의 주어진 범위 안에서 소수를 구하는 문제였다. 해당 문제를 for 문을 통한 완전탐색으로 풀이가 가능하지만, 해당 문제의 경우 입력값 최대 값이 1,000,000이므로 시간 초과가 일어난다. 

서로소는 약수가 1과 자기 자신만이 있는 수를 말한다. 이 말은 해당 수가 1과 자기 자신 외에 나누어 지면 안된다는 뜻이다. 대체로 서로소가 아닌 수의 약수 값을 보면 해당 수의 루트 값을 중심으로 대칭을 이루는 것을 확인할 수 있다.

25: 1, 5(25의 루트값), 25

12: 1, 2, 3, 4, 6, 12 (12의 루트 값인 3.xx 값을 중간으로 대칭을 이루고 있다. )

따라서 주어진 범위 내의 한 숫자인 i 값을 받은 후, 해당 i 값의 루트 값까지만 검사하면 해당 수의 소수 여부를 알 수 있다. 

이후 해당 수가 소수라면 출력한다. 

 

오늘의 회고

에라토스테네스의 체 (Sieve of Eratosthenes) 알고리즘

에라토스테네스의 체란?

에라토스테네스의 체(Sieve of Eratosthenes)는 소수를 빠르게 찾는 알고리즘이다.
기본적인 소수 판별법(완전 탐색을 통한 약수 검사)을 사용하면 O(√N)의 시간이 걸리지만,
이 알고리즘은 O(N log log N)의 시간 복잡도로 훨씬 빠르게 동작한다.

---

알고리즘 동작 원리

1) 2부터 시작해서 특정 숫자의 배수를 모두 제거
2) 제거되지 않은 수는 소수이므로 기록
3) 반복하면서 남아있는 수를 찾으면 소수 리스트 완성

예제 (1~30까지 소수 찾기)

1. 2는 소수 → 2의 배수(4, 6, 8...) 제거
2. 3은 소수 → 3의 배수(6, 9, 12...) 제거
3. 4는 이미 제거됨 → 패스
4. 5는 소수 → 5의 배수(10, 15, 20...) 제거
5. 반복

새로운 개념인 에라토스테네스의 체에 대해 배울 수 있어 좋았다!!