[프로그래머스] - 소수 찾기 (Kotlin && JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/12921?language=java 

프로그래머스

문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건
n은 2 이상 1000000 이하의 자연수입니다.

 

풀이(Kotlin)

 class Solution {
   fun solution(n:Int):Int{
       val checked = BooleanArray(n+1)
       checked[0] = true
       checked[1] = true
       for (i in 2 .. sqrt(n.toDouble()).toInt()){
           if (checked[i]) continue
           for (j in i + i .. n step i){
               checked[j] = true
           }
       }
       return checked.count { !it }
   }
}

• 해당문제를 Boolean배열을 이용하여 풀어보았습니다.
• 소수라는것은 결과적으로 약수가 본인자신과 1밖에 있을 경우 해당숫자는 소수라고 말합니다. 그렇다면 소수의 배수의 값들은 소수일 수 없습니다.
• 여기서 추가로 sqrt함수 즉 재곱근한수를 쓰는 이유는 기준인 i 가 sqrt(n)을 넘게 되면 j 가 될 수 있는 값의 최대는 i*i를 넘을 수는 없습니다. 즉 이미 한번 j라는 값의 연산을 하였기에 sqrt(n)을사용합니다.
• 수식으로 말하자면 j = i * k라고 할때 k < i 라면 이전에 i가 k일 때 k*i를 이미 true로 넣어주기 때문에 sqrt함수의 한 번의 동작으로 중복되는 반복을 줄일 수 있습니다. 결과적으로 모든 박복문을 끝내고 배열에서 false인 값의 개수는 소수의 개수와 같습니다.

풀이(Java)

class Solution {
    public int solution(int n) {
        boolean[] checked = new boolean[n + 1];
        checked[0] = true;
        checked[1] = true;
        for (int i = 2; i <= (int) Math.sqrt(n); i++) {
            if (checked[i]) continue;
            for (int j = i + i; j <= n; j += i) {
                checked[j] = true;
            }
        }
        int count = 0;
        for (boolean isPrime : checked) {
            if (!isPrime) count++;
        }
        return count;
    }
}

• 해당 문제는 Kotlin코드를 받지 못하기때문에 Java코드로 변환하여 제출해 보았습니다.

결과