[프로그래머스][Kotlin] 합성수 찾기

목차

 

문제 정보

https://school.programmers.co.kr/learn/courses/30/lessons/120846

프로그래머스

난이도 : Lv0

유형 : 정수론

---

문제 풀이

이 문제는 n이 최대 100이여서 완전탐색으로도 쉽게 풀 수 있지만

소수를 이용하면 최적화 시킬 수 있다.

 

필자는 에라토스네테스의 체를 이용하였다.

---

코드

class Solution {
    fun solution(n: Int): Int {
        var answer: Int = 0
        var primes = BooleanArray(n + 1);

        for (i in 2..Math.sqrt(n.toDouble()).toInt()) {
            if (!primes[i]) {
                for (j in i * 2..n step (i)) {
                    primes[j] = true
                }
            }
        }

        for (i in 1..n) {
            if (primes[i]) {
                answer++
            }
        }

        return answer
    }
}