/* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */
참고 자료
[백준] 1929번 - 소수 구하기 : https://www.acmicpc.net/problem/1929
문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
1. Mysolution
fun isPrimeNum(n : Int): Boolean{
if (n == 1) return false
if (n == 2) return true
for (i in 2 until n){
if (n % i == 0) return false
}
return true
}
fun main() {
val sb = StringBuilder()
readLine()!!
.split(' ')
.map{ it.toInt() }
.let{ (a,b) ->
for (num in a..b) {
if(findPrimeNum(num)) sb.append(num).append("\n")
}
}
}결과는 시간 초과이다.
시간 단축을 위해 StringBuilder로 String 자료형으로 한 번에 출력을 시도했다. 하지만 결과는 fail.. 이대로는 시간 단축에 한계가 있음을 깨닫고 인터넷에 검색을 해봤다. 소수를 좀 더 빠르게 구하는 혁신적인 방법으로 '에라토스테네스의 접근(체)' 방법이 있다는 것을 알게 되었다.
2. 에라토스테네스의 체
'에라토스테네스 체'의 정의는 다음과 같다.
모든 자연수는 소수들의 곱으로 표현이 된다. 제일 작은 소수 2부터 시작한다. 2부터 N-1까지의 수 중에서 2의 배수를 모두 체로 거르고 남은 숫자들 중에서 3의 배수로 거르고를 반복해서 제곱근N 까지 나눠서 걸러지지 않고 남은 수들이 모두 소수가 된다.
주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문이다.
[출처] : https://jongmin92.github.io/2017/11/05/Algorithm/Concept/prime/
우선, 2부터 N의 제곱근 까지 나눴을 때 안 나눠지면 소수라고 할 수 있다.
fun quickFindPrimeNumSol1() {
val NM = readLine()!!.split(" ")
val N = NM[0].toInt()
val M = NM[1].toInt()
// prime(index) 여부를 저장하는 array
val check = BooleanArray(M + 1){true}
for (num in N..M){
val sqrt = sqrt(num.toDouble()).toInt()
// 2부터 N의 제곱근까지의 수까지 나눠서 나누지면 반복문 종료
for (i in 2..sqrt){
if (num % i == 0) {
check[num] = false
break
}
}
}
for (i in N..M){
if (i == 1) continue
if (check[i]) println(i)
}
}이제 시간초과가 안 뜬다. 하지만 여전히 위 코드는 효율적이지 못하다. 왜냐하면 하나의 수(num) 에 대해 소수인지 아닌지 판단하기 때문에 N..M 범위 안에 있는 수만큼 확인한다.
우리가 만약 1 부터 100 안에 소수를 찾기 위해서 1부터 100까지 소수임을 확인하는 것은 효율적일까? 당연히 아닐 것이다. 2의 배수인 4,6,8... 등 짝수를 확인할 필요가 없다. 마찬가지로 3의 배수(6,9,12...) 또한 확인할 필요가 없다. 결국 2부터 10(100의 제곱근)의 배수를 체에 걸르듯 소수에서 걸러내면 된다. 그렇게 되면 결국 1 부터 100 사이의 소수만 남게 된다. (이 설명으로도 이해가 되지않는다면 다음 [글] 을 읽어보자.)
'에라토스테네스의 체'를 이용해 코드를 좀 더 개선해보자.
fun quickFindPrimeNumSol2() {
val NM = readLine()!!.split(" ")
val N = NM[0].toInt()
val M = NM[1].toInt()
// index 에 따라 prime 여부를 저장하는 array
val prime = BooleanArray(M + 1){true}
val sqrtOfM = sqrt(M.toDouble()).toInt()
// 2의 배수, 3의 배수, ... sqrt의 배수를 걸러낸다.
for (i in 2..sqrtOfM){ //(1)
var j = 2
while (i*j <= M){
if (prime[i*j]) prime[i*j] = false
j++
}
}
for (i in N..M){
if (i == 0 || i == 1) continue
if (prime[i]) println(i)
}
}실행 결과
코드의 성능이 대폭 상승했다! 그러나 아직 부족하다.. 여기서 더 개선할 수는 없을까?
내가 개선할 수 있다고 생각하는 부분은 1번 위치의 코드이다.
그 이유는 for (i in 2..sqrt) 에서 2 부터 N의 제곱근까지의 수까지 나눈다. 에라토스네테스 체의 정의에 따르면 2 부터 N의 제곱근 범위 안에 있는 '소수'의 배수만 제거하면 된다. 예시를 들어 좀 더 쉽게 설명해보겠다.
지금 우리는 2의 배수, 3의 배수, 4의 배수(비교할 필요 x) , 5의 배수 ... sqrt(가장 큰 값의 제곱근)의 배수를 확인한다. 그렇다면 4의 배수는 이미 2의 배수에서 걸러졌기 때문에 굳이 확인할 필요가 없다는 것이다.
그렇다면 (1) 에서 2..sqrtOfM 범위의 소수만 가져온다면 비교횟수는 줄어들지 않을까? 한 번 시도 해보자.
<삽질 1>
fun quickFindPrimeNumSol3() {
val NM = readLine()!!.split(" ")
val N = NM[0].toInt()
val M = NM[1].toInt()
// index 에 따라 prime 여부를 저장하는 array
val prime = BooleanArray(M + 1){true}
val sqrt = sqrt(M.toDouble()).toInt()
val primeInSqrt = getPrimeArr(sqrt)
// 2의 배수, 3의 배수, 5의 배수 ... sqrt 보다 작은 소수의 배수를 걸러낸다.
for (i in 2 until primeInSqrt.size){
if (primeInSqrt[i]){
var j = 2
while (i*j <= M){
if (prime[i*j]) prime[i*j] = false
j++
}
}
}
for (i in N..M){
if (i == 0 || i == 1) continue
if (prime[i]) println(i)
}
}
fun getPrimeArr(size: Int) : BooleanArray{
val prime = BooleanArray(size + 1){true}
val sqrt = sqrt(size.toDouble()).toInt()
for (i in 2..sqrt){
var j = 2
while (i*j <= size){
if (prime[i*j]) prime[i*j] = false
j++
}
}
return prime
}실행 결과
(1) 위치에 제곱근 범위 안에 있는 소수를 반환할 생각만하다보니 메모리도 더 많이 쓰고 이로 인해 성능도 개선이 안 됐다. 다시, 생각해보니 굳이 sqrt 범위 안에 있는 배열을 새로 만들 필요가 없었다. 이미 prime 에 정보가 있기 때문에 다음과 같이 한 줄만 추가하면 된다.
<최종>
fun quickFindPrimeNumSol4() {
val NM = readLine()!!.split(" ")
val N = NM[0].toInt()
val M = NM[1].toInt()
// index 에 따라 prime 여부를 저장하는 array
val prime = BooleanArray(M + 1){true}
val sqrtOfM = sqrt(M.toDouble()).toInt()
// 2의 배수, 3의 배수, 5의 배수 ... sqrt의 배수를 걸러낸다.
for (i in 2..sqrtOfM){ //(1)
// 이미 지워진 경우
if (!prime[i]) continue // <-- 추가한 부분
// 소수의 배수 제외
else {
var j = 2
while (i*j <= M) {
if (prime[i * j]) prime[i * j] = false
j++
}
}
}
for (i in N..M){
if (i == 0 || i == 1) continue
if (prime[i]) println(i)
}
}
실행 결과
실행 결과, 코드가 좀 더 개선된 것을 확인할 수 있다. 위 코드로 '에라토스테네스 체' 구현에 성공했다.
에라토스테네스 체 알고리즘 습득 완료
