백준 1016번 with Kotlin #에라토스테네스의 체

제곱 ㄴㄴ 수 성공출처

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

35789

6113

4094

19.836%

문제

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다.

제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

예제 입력 1 복사

1 10

예제 출력 1 복사

7

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

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

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.sqrt
 
 
val br = BufferedReader(InputStreamReader(System.`in`))
 
fun main()=with(br){
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val (min,max) = readLine()!!.split(" ").map{it.toLong()}
    val size = (max - min +1).toInt()
    var list = MutableList<Long>(size,{-1})
    val sqrt = sqrt(max.toDouble()).toInt() // 1 2 3 4 5 6 7 8 9 10 => root(10) 4, 9 -> 2,3   max 1000001000000
    val key = MutableList(sqrt+1,{-1})
    val key2 = mutableListOf<Long>()
    for(i in 2 .. sqrt){ // 어떠한 수의 제곱으로 만들어지지 않는 수 = 초기 수 , 초기수는 0으로 만들지 않고 초기수로부터 제곱되어지는 수는 0으로 만드는 것.
        if(key[i]==0)
            continue
        for(j in i+i .. sqrt step i) // 초기 수의 배수는 0으로 만들어주는 작업을 한다.
            key[j]=0
    }
    for(i in 2 .. sqrt){ //어떠한 수의 배수들은 값으로 0으로 들어가고 초기수는 -1이라는 값이 남아있을건데, max 1000001000000를 기준으로
        // sqrt를 구하게된다면 1000000번을 돌 수는 없으니까 시간을 줄이기 위해서 에라토스의 체라는 개념을 사용해서 초기수만 남기는 작업을했습니다.
        // 4의 제곱인 16은 2의제곱은 4이기 때문에 굳이 2번 연산을 할 필요가 없다고 생각했습니다.
        if(key[i]!=0){
            key2.add(i.toLong())
        }
    }// 초기수만 key2라는 list에 남게 된다.
   // println(key2)
   // println(key.size)
   // println(key2.size)
    for(i in 0 until size){ //1000000000000 1000001000000 mapping을 하자.
        // 1000001000000 - 1000000000000 + 1 = size list[0]=min값이다. list[1] = min+1
            // size를 구할때 +1을 한 이유는 3 ~ 11 값을 구할때, 3 4 5 6 7 8 9 10 11 9개다 라고 구할 수 있고, 11 - 3 + 1 = 9개
        list[i]=min+i
    }
    //println(list)
    var count = 0
    for(i in 0 until key2.size){
        var go : Long = key2[i]*key2[i]
            //println("go: $go")
            var gg = min
            var index = 0L
            if(gg%go==0L)
                index=0L
            else{ // go = 4 , min = 3 , max = 10  list[0]=3  gg = 3 , go - (gg%go) = 4 - (3%4) = 1 , list[1] = 4
                // go = 4 , min = 4 , max = 10  gg= 4 go =4
                index=go-(gg%go)
            }
            for (k in index until list.size step go) { // go = 4 , 4의 배수인 8 12 16
               // println("K: $k")
                list[k.toInt()] = 0
            }
    }
    for(i in 0 until list.size){
        if(list[i]!=0L)
            count++
    }
   // println(list)
    println(count)
 
 
    //println(list)
 
 
    bw.flush()
    bw.close()
}