[백준][Kotlin] 1456번 거의 소수

해당 문제는에라토스테네스의 체 원리를 응용하여 작성할 수 있습니다.

에라토스테네스의 체를 간단히 설명하자면 예를 들어 0~30까지 숫자 중 소수를 찾고 싶다면

31개의 1차원 배열을 생성 후 2 부터 시작하여 그 수의 배수들을 모두 소수가 아닌 수 처리를 하여 소수를 찾아내는 기법입니다.

 

아래 그림은 이해하기 쉽도록 1~30으로 표현하였습니다.

1(소수x)	2(시작)	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

 

1(소수x)	2(시작)	3		5		7		9
11		13		15		17		19
21		23		25		27		29

 

1(소수x)	2	3(시작)		5		7
11		13				17		19
		23		25				29

 

1(소수x)	2	3		5(시작)		7
11		13				17		19
		23						29

이런식으로 배수들을 삭제하여 소수들을 찾는 것이 에라토스테네스의 체의 원리 입니다.

 

그리고 문제의 제한 조건을 보면

• 1 ≤ A ≤ B ≤ 10^14

이라는 문구가 있습니다. 소수를 구할때는 2 부터 최대값의 제곱근 까지 에라토스테네스의 체의 원리를 이용하여 구하면 되므로 먼저 10^7 size+1를 가진 배열을 생성 후 각 인덱스별로 인덱스 값을 넣어 줍니다.

그리고 만든 배열을 인덱스 2부터 조회하면서 2의 배수에 해당하는 인덱스의 값들을 소수가 아님을 표시하면서 소수가 아닌 수들을 걸러 냅니다. 저의 경우 소수가 아니면 0으로 변경 하였습니다. 2부터 조회한 이유는 0과1은 소수가 아니기 때문입니다. 이 과정을 진행하게 되면 배열에는 1를 제외한 소수가 아닌 수들은 모두 0으로 변경되었음을 알 수 있습니다.

 

그리고 이제 소수의 N제곱이 두 정수 A와 B 사이에 포함 되는지 확인하는 것만 하면 되는데 숫자가 크다보니 계산 중 오버플로우 가 발생하여 원하는 결과 값이 안 나올수 있기 때문에 A와B를 비교하려는 값(제곱하기 이전값) 으로 나누면서 계산하면 오버플로우가 발생하지 않도록 할 수 있습니다.

이때 나누면 소수점이 발생 할 수 있기에 자료형은 double 혹은 float로 변경하여 계산합니다.

 

하기는 작성한 코드와 제출 결과 입니다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.math.sqrt


fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    //var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    var N = st.nextToken().toLong()
    var M = st.nextToken().toLong()
    var arr = LongArray(10000001){0}

    for(i in 0 .. arr.size-1){
        arr[i] = i.toLong()
    }

    for(i in 2 ..Math.sqrt(arr.size.toDouble()).toInt()+1){
        if(arr[i] == 0L){
            continue
        }
        for(j in i+i .. arr.size-1 step i){
            arr[j] = 0L
        }
    }

    var count = 0
    for(i in 2 .. 10000000){
        if(arr[i] != 0L){
            var temp = arr[i]
            while(arr[i]<= M.toDouble() /temp.toDouble() ){
                if(arr[i].toDouble()  >= N.toDouble()/temp.toDouble() )count++
                temp *= arr[i]
            }
        }
    }
    println(count)


    //bw.flush()
    //bw.close()
}