[Swift] 소수 판별

 

func isPrime(_ number:Int) -> Bool {
    if number < 2 {
        return false
    }

    for i in 2...(number - 1) {
        if number % i == 0 {
            return false
        }
    }
    return true
}

 

이 경우 시간 복잡도는 O(n)

-> 제곱근 까지만 확인해도 된다. (약수는 제곱근을 기준으로 대칭이므로)

import Foundation

func isPrime(_ number:Int) -> Bool {

	if number < 2 {
        return false
    }

    for i in 2..<Int(sqrt(Double(number)) + 1) {
        if number % i == 0 {
            return false
        }
    }
    return true
}

print("\(isPrime(7))") //true

이 경우 시간 복잡도는 O(√n)