알고리즘 문제 풀이/백준

[Algorithm] 백준 - 소수 찾기 (1978) (Kotlin)

참깨빵위에참깨빵_ 2024. 9. 19. 15:53
728x90
반응형

 

소수는 1보다 크면서 약수가 1과 자기 자신뿐인 숫자를 말한다. 2번째 입력에서 이 소수의 숫자를 카운트해서 출력하면 된다.

 

fun main() {
    val N = readln().toInt()
    val nums = readln().split(" ").map { it.toInt() }
    var primeCount = 0

    for (num in nums) {
        if (isPrime(num)) {
            primeCount++
        }
    }
    println(primeCount)
}

fun isPrime(x: Int): Boolean {
    if (x < 2) return false
    for (i in 2..Math.sqrt(x.toDouble()).toInt()) {
        if (x % i == 0) return false
    }
    return true
}

 

소수 구하는 로직을 함수로 따로 뺐다. 소수면 true, 소수가 아니면 false를 리턴하는 함수로, 함수 본문 처음에 2보다 큰 숫자여야 하기 때문에 1 이하의 정수를 받으면 false를 리턴하게 했다. 이 처리가 있어야 1을 소수로 인식하지 않는다.

그리고 sqrt()를 써서 2부터 매개변수 x까지의 제곱근을 반복하면서 나눠떨어지는지 확인한다. 나눠떨어진다면 그 숫자는 소수가 아니기 때문에 false를 리턴한다.

 

무슨 말이냐면 앞서 소수는 1보다 크면서 1과 자신만을 약수로 갖는 숫자라고 했다. 5는 1, 5로만 나눌 수 있어서 소수다.

이렇게 숫자가 소수인지 아닌지 판단하는 방법 중 하나는 어떤 숫자를 2부터 5 직전까지의 숫자들로 나6누는 것이다.

어릴 때 한 번쯤은 해봤을 암산으로 약수 구하기 놀이인데, 가령 36이란 숫자가 주어지면 맨 처음과 마지막에 1과 36을 쓰고, 1 오른쪽에 2를 쓴 다음 36의 왼쪽에 18을 쓴다.

 

  • 1                         36
  • 1 2                 18 36
  • 1 2 3         12 18 36

 

이런 식으로 가운데 빈 공간에 숫자들을 써 가면서 약수들을 구하는 놀이다. 하지만 예를 들어 1,246,864같은 큰 수를 받으면 계산이 많이 발생하게 된다.

이 계산을 줄이려면 제곱근을 확인하는 방법을 쓸 수 있다. 36의 경우 약수들은 아래와 같다.

 

  • 1, 36
  • 2, 18
  • 3, 12
  • 4, 9
  • 6, 6

 

이 때 36의 제곱근인 6을 넘는 약수는 반드시 6보다 작은 약수와 짝을 이룬다. 6보다 큰 7, 8, 9 같은 숫자는 확인할 필요가 없다. 만약 36을 8로 나눌 수 있었다면 8과 짝을 이루는 약수가 이미 존재했어야 한다.

그래서 36의 경우 6보다 큰 숫자는 확인할 필요가 없다. 그래서 제곱근만 확인할 수 있다면 소수 여부를 판단하는 힌트로 쓸 수 있다.

 

테스트 케이스인 1, 3, 5, 7을 대상으로 isPrime()을 실행하면 아래처럼 작동한다.

 

  • 1
    • if (x < 2) 조건에 걸려서 false를 리턴 = 소수가 아니다
  • 3
    • Math.sqrt()에 넣으면 1이 나온다 -> 반복문은 for (i in 2 .. 1)가 된다 -> 비어 있는 범위라서 반복문이 실행되지 않는다
    • 반복문을 탈출하고 true를 리턴한다 = 소수다
  • 5
    • Math.sqrt()에 넣으면 2가 나온다 -> 반복문은 for (i in 2 .. 2)가 된다 -> 2만 갖고 반복문이 작동한다
    • 5 % 2로 나머지를 구하면 0이 아니다 -> 소수다
  • 7
    • Math.sqrt()에 넣으면 3이 나온다 -> 반복문은 for (i in 2 .. 3)가 된다 -> 2, 3으로 반복문이 작동한다
    • 7 % 2, 7 % 3으로 나머지를 구하면 모두 0이 아니다 -> 소수다
  • 3, 5, 7만 소수기 때문에 3을 출력한다 -> 프로그램 종료
반응형