백준 1418 k-세준수(Kotlin)

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

1418번: K-세준수

문제 접근

n이하의 자연수 중에 소인수의 최대값이 k보다 작은 수가 몇개인지 구하는 문제

판별하는 수의 약수 중 소수의 최대값이 k보다 작으면 k-세준수로 판별

 

작성한 코드(시간초과)

fun main(args: Array<String>): Unit = with(Scanner(System.`in`)) {
    val n = nextInt()
    val k = nextInt()
var ans = 0
    for(i in 1..n){
        var max = 0 //소인수 중 최대값
        for (j in 1..i){ //i가 세준수인지 판별
            if(isPrime(j) && i%j ==0){ //i의 소인수인지 판별
                if (max <j) max = j // 소인수의 최대값 저장
            }
        }
        if (max <= k) ans++
    }
    print(ans)
}

fun isPrime(num:Int):Boolean{
    if (num == 1 || num == 2)return false
    for (i in 2..num/2){ //
        if (num%i ==0) // 2로 나누어 떨어지면 소수 아님
            return false
    }

    return true
}

에라토스테네스의 체(소수 구하는 알고리즘)을 활용해서 구현했는데 시간초과됨...

 

결국 다른사람 풀이 참조...

fun main(args: Array<String>): Unit = with(Scanner(System.`in`)) {
    val n = nextInt()
    val k = nextInt()
    val arr = IntArray(n+1)
    var ans = 0
    for (i in 2..n){
        if (arr[i] != 0)continue

        for (j in i..n step i){
            arr[j] = Math.max(arr[j], i)
        }
    }
    for (i in 1..n){
        if(arr[i] <= k)
            ans++
    }

    print(ans)
}

 

 

 

참고한 자료

https://tarotaro90.com/ko/%EB%B0%B1%EC%A4%80-01418-k-%EC%84%B8%EC%A4%80%EC%88%98-java%EC%9E%90%EB%B0%94/

[백준] 01418 K-세준수 - Java(자바) - Taro's Sundries

비고

에라토스테네스의 체를 그냥 가져다 쓰는게 아니라 원리를 활용해서 구현하는 문제였나봄...

다음에 다시 해보자...