[algorithm] 백준 1929 - 소수 구하기

[algorithm] 백준 1929 - 소수 구하기

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 문제 1929번에 대한 풀이를 가지고왔습니다.

 

풀이를 보기전에 먼저 최대한 고민도 해보고 이런 저런 시도를 해보신 다음에

 

정답을 맞췄다면 시간이 얼마나 걸렸나를 확인해보고 그렇지 못 할 때는 풀이를 보면서

 

어떤식으로 문제를 풀어가는가를 살펴보면서 문제해결능력을 길러봅시다.

 

문제 풀이로 넘어가겠습니다.

 

알고리즘

---

백준 BAEKJOON 1929

 

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

 

1929번: 소수 구하기

 

문제 해석

 

주어진 자연수 구간에 존재하는 소수를 모두 출력하는 문제입니다.

문제에서는 에라토스테네스의 체 를 사용하거나 4134번 문제인 '다음 소수' 문제의 풀이를

이용하라고 나와있는데 우리는 둘다 시도해보겠습니다.

 

풀이 1 - 에라토스테네스의 체

 

m, n = map(int, input().split())

sieve = [True] * (n+1)
sieve[0], sieve[1] = False, False

for i in range(2, int(n ** 0.5) + 1):
    if sieve[i] == True:
        for j in range(i+i, n+1, i): # i이후 i의 배수들을 False 판정
            sieve[j] = False

for i in range(m, n+1):
    if sieve[i] == True:
        print(i)

---

 

풀이 2 - 단순하게 소수 판별 후 출력

 

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)

 

풀이 해석 및 팁

 

풀이 1번

에라토스테네스의 체를 사용해 문제를 해결했습니다.

처음에 sieve 리스트에 총 n+1개의 True를 요소로 가지게끔 초기화해줍니다.

그리고 0과 1은 소수가아니므로 바로 False로 수정해준 다음에 2부터는 체에 거르듯이 한번 소수로 체크된 수의

배수들은 모두 False로 바꾸어주면서 문제에서 원하는 구간안에서 소수를 추려나갑니다.

이때 검사하는 구간은 약수의 대칭성을 이용할 수 있도록 (n ** 0.5)까지만을 검사하면 되겠습니다.

제곱근보다 작은 약수까지 구해놓으면 그 뒤로는 대칭성을 이루기 때문에 소수를 구할 때는 여기까지만

검사해도 소수 판별에 지장이 없습니다.

이렇게 체에 거르듯 소수가 아닌 수들을 하나 하나 걸러가면서 구간에 존재하는 소수를 출력하면 문제 해결.

---

풀이 2번

단순하게 구간에 존재하는 수 하나 하나를 소수인지 아닌지를 검사하면서 소수일 경우에 출력하게끔

반복문을 구성하여 문제를 해결했습니다.

소수를 판별할 때 검사해야할 구간은 해당 숫자의 제곱근까지로 지정해 약수가 있는지를 판별합니다.

약수가 없다면 소수이므로 해당 숫자를 출력하고 약수가 있다면 다음 수로 넘어가게끔 반복문을 구성했습니다.

---

여기까지 백준 1929번 - 소수 구하기 문제의 풀이였습니다.

 

에라토스테네스의 체는 소수를 구하는 문제에서 자주 사용되는 개념이므로

 

확실하게 이해하고 사용하시면 유용하게 써먹을 수 있는 좋은 방법입니다.

 

꼭 올바르게 숙지하셔서 알맞게 사용하시길 바랍니다.

 

감사합니다.