백준 - 1929 소수 구하기 풀이

문제

1929 소수 구하기

소수란?

• 소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.[소수 (수론)]

소수 판별 방법

풀이

개념

• 특정 수가 소수인지를 판별하기 위해서는 1보다 크고 자기 보다 작은 모든 수로 자기 자신을 나눴을 때 나머지가 없는 수가 있는지 확인하면 된다.

  fun Int.isPrimeNum(): Boolean {
    for(i in 2 until this)
        if(this % i == 0) return false
    return true
  }
  

  최적화

• 정말 “1보다 크고 자기 보다 작은 모든 수”를 대상으로 확인을 해야 할까?
• 사실 어떤 자연수 n이 소수임을 판정하기 위해서 ⌊√n⌋까지만 진행하면 되는데, 수가 수를 나누기 위해서는 그 몫이 항상 필요하며 나누는 수와 몫 중 어느 하나는 반드시 √n이하이기 때문이다.[소수 (수론)]

  예)

  1. 64의 약수는 1, 2, 4, 8, 16, 32, 64 이다. 즉, 64 = 1 * 64 = 2 * 32 = 4 * 16 = 8 * 8 이다. 즉, 2, 4, 8만을 대상으로 확인하면 소수인지 여부가 판별이 가능하다. 2, 4, 8은 모두 ⌊√64⌋ = 8 이하이다.
  2. 90의 약수는 1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90 즉, 90 = 1 * 90 = 2 * 45 = 3 * 30 = 5 * 18 = 6 * 15 = 9 * 10 즉, 2, 3, 5, 6, 9 만으로 대상으로 확인하면 소수인지 여부가 판별이 가능하다. 2, 3, 5, 6, 9는 모두 ⌊√90⌋ = 9 이하이다.

• “1보다 크고 자기 보다 작은 모든 수” 즉, (n - 2)번이 아닌 ⌊√n⌋번의 연산만 하면 된다.

  예) n = 97일 경우 95번(2 until 97)의 연산이 아닌 8번(2 .. 9)의 연산만 하면 된다.

  fun Int.isPrimeNum(): Boolean {
    val other = kotlin.math.sqrt(this.toDouble()).toInt()
    for(i in 2..other)
        if(this % i == 0) return false
    return true
  }
  

답

kotlin code

fun main() {
    val input = readln().split(" ").map { it.toInt() }
    for(i in input[0] .. input[1])
    {
        if(i.isPrimeNum()) println(i)
    }
}

fun Int.isPrimeNum(): Boolean {
    if(this < 2) return false
    if(this == 2) return true
    val other = kotlin.math.sqrt(this.toDouble()).toInt()
    for(i in 2..other)
        if(this % i == 0) return false
    return true
}

에라토스테네스의 체 방법

풀이

에라토스테네스의 체 알고리즘

1. 찾고자 하는 범위의 자연수를 나열한다.
2. 1은 지운다.
3. 2부터 시작하여, 2의 배수를 지워나간다.
4. 다음 소수의 배수를 모두 지운다. [[소수 (수론)](https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0))]

답

kotlin code

fun main() {
    val input = readln().split(" ").map { it.toInt() }
    val isPrimeNumbers = BooleanArray(input[1] + 1) { true }
    isPrimeNumbers[0] = false
    isPrimeNumbers[1] = false
    val limitNumber = kotlin.math.sqrt(input[1].toDouble()).toInt()

    for(number in (2..limitNumber))
    {
        if(!isPrimeNumbers[number]) continue
        val powerOfNumber = number * number
        for (y in (powerOfNumber until isPrimeNumbers.size) step number) {
            isPrimeNumbers[y] = false
        }
    }

    for(i in (input[0]..input[1])) {
        if(isPrimeNumbers[i]) println(i)
    }
}

Reference

• 소수 (수론)
• 에라토스테네스의 체