Swift - 백준 1929 소수 구하기

1과 2를 제외한 수로 나눌 수 없는 수를 소수라고 합니다

 

소수에는 1, 2, 3, 5, 7, 11, 13 ... 등의 숫자들이 존재합니다.

 

소수인 수를 구하기 위해서는 "에라토스테네스의 체" 를 사용해서 구하는 방법을 사용해야 합니다.

 

에라토스테네스의 특징

에라토스테네스의 체란 다음과 같은 특징을 가지고 있습니다.

• 2를 제외한 2의 배수를 모두 지웁니다.
• 3을 제외한 3의 배수를 모두 지웁니다.
• 5를 제외한 5의 배수를 모두 지웁니다.
• 7을 제외한 7의 배수를 모두 지웁니다.
• 이후 11과 13과 같이 소수들을 제외한 해당 배수들의 수를 모두 지워줍니다.

에라토스테네스의 한계

에라토스테네스의 한계로는 위에서 확인했듯이 만약 1부터 120까지의 수 중에서 소수를 찾아낼 때는 2를 제외한 2의 배수와 3을 제외한 3의 배수, 5를 제외한 5의 배수, 7을 제외한 7의 배수까지만 구하면 됩니다. 그렇다면 다음과 같이 코드를 만들 수 있겠습니다.

var line = readLine()!.split(separator: " ").map { Int($0)! }

for i in line[0]...line[1] {
    if (i != 1) && ((i==2) || i%2 != 0) && ((i==3) || (i%3 != 0)) && ((i == 5) || (i%5 != 0)) && ((i == 7) || (i%7 != 0)) {
        print(i)
    }
}

 

하지만 만약 숫자가 1000까지 존재한다면 11 뿐만 아니라 13과 그 이상의 값들을 제외한 해당 값의 배수 값들을 제외한 값을 출력해줘야 하며 이는 조건문이 매우 크게 늘어나며 직접 타이핑하기에는 무리가 생깁니다. 즉 특정 범위 내의 소수를 판정하는 데에만 효율적이라고 할 수 있습니다.

 

제곱근을 이용하여 소수 구하기

다음은 제곱근을 사용하여 소수를 구하는 방법을 소개하겠습니다.

 

• 먼저 isPrimeNumber 함수를 만듭니다.
• 함수 내에서는 1이면 false를 리턴합니다.
• 2 보다 크고 주어진 값의 제곱근까지의 값 중 인자값n 과의 나머지 값이 0인 값을 추려냅니다.
  • 제곱근까지의 값까지 검사하는 이유는 소수의 특성상 제곱근 이상의 약수는 필요없기 때문입니다.
  • 만약 if n%i == 0 이 나눠 떨어진다면 약수가 존재하는 것이기 때문에 false를 반환합니다.
• 함수에서 반환값이 true라면 해당 값은 소수이므로 출력하고 false라면 출력을 하지 않습니다.

 

import Foundation

func isPrimeNumber(n: Int) -> Bool {
    if n == 1 {
        return false
    }
    for i in 2..<Int(sqrt(Double(n)) + 1) {
        if n % i == 0 {
            return false
        }
    }
    return true
}
let input = readLine()!.split(separator: " ").map { Int($0)! }
let m = input[0]
let n = input[1]

for i in m...n {
    if isPrimeNumber(n: i) {
        print(i)
    }
}