소수 판별 알고리즘

• 기본 : 약수 성질 이용, 제곱근사용 -> Foundation 필요
  
  

import Foundation

func isPrime(_ num: Int) -> Bool {
    
    if num < 4 {
        return num == 1 ? false : true
    }
    
    for i in 2...Int(sqrt(Double(num))) {
        if num % i == 0 {
            return false
        }
    }
 
    return true
}

 

• 에라토스테네스의 체 + 골드바흐 
  
  

import Foundation

let T = Int(readLine()!)!

// 에라토스테네스의 체, n이 4이상이라는 조건이 있어서 n < 4 예외처리를 제외
// 조건을 잘 확인하고 관련한 조건을 꼭 충족시켜줘야 한다.

func seiveEratos(_ n: Int, _ primes: inout [Bool]) {
    for i in 2...Int(sqrt(Double(n))) {
        for j in 2 ... n / i {
            primes[i*j] = false
        }
    }
}

for _ in 1...T {
    let n = Int(readLine()!)!
    var isPrimes = Array(repeating: true, count: n + 1)
    seiveEratos(n, &isPrimes)
    
    // 골드바흐의 추측
    
    for i in n/2...n {
        if isPrimes[i] {
            let rest = n - i
            if isPrimes[rest] {
                print("\(rest) \(i)")
                break
            }
        }
    }
    
}

 

소수 판별 알고리즘도 자주 출제되는 유형 중에 하나라고 한다. 이해 및 개념을 잡아두고 소수 관련한 문제에 사용해보자!