[Function] isPrime - 소수판별

Function / isPrime - 소수판별

---

목표

정수 num이 소수인지 판별하기

 

소수 : Prime Number - 1 보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 자연수, 무리수

 

구현

github

GitHub - keeplo/SwiftTools: 자료구조 알고리즘 등 직/간접적으로 사용가능한 예제

//	Swift 5
//  Created by Yongwoo Marco 21.05.31
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
}

 

약수 확인을 이용해서 판별했다.

2와 5를 제외하면, 모든 소수의 일의 자리 수는 1, 3, 7, 9이다. 어떤 자연수 이 소수임을 판정하기 위해선 √n까지의 수 중 1을 제외하고 그 자연수의 약수가 있는지 확인하면 된다. 배수의 성질을 이용하면 쉽게 구할 수도 있다. _ Wikipedia 소수 골라내기 방법

 

추가적으로 생각해볼 내용

단순히 몇개의 수를 확인할때는 해당 함수를 사용하겠지만 

메모리나 시간에 민감할정도로 많은 수를 확인할때는 에라토스테네스의_체를 이용해서

나올 수 있는 수의 최대 수까지 미리 판별하는 방법도 있다

// 	Swift 5
//  Created by Yongwoo Marco 21.05.31
import Foundation

var check = [Bool]()

func sieveOfEratosthenes(_ maxNum: Int, _ check: inout [Bool]) {
    check = [Bool](repeating: true, count: maxNum + 1)

    for i in 2...Int(sqrt(Double(maxNum))) {
        for j in 2...maxNum/i {
            check[i*j] = false
        }
    }
}

// 에라토스테네스의 체 - 999까지
sieveOfEratosthenes(999, &check)

func displayPrimes(_ check: [Bool]) -> [Int] {
    var primes = [Int]()
    for (i, v) in check.enumerated() {
        if v == true {
            primes.append(i)
        }
    }
    
    primes.removeFirst()
    primes.removeFirst()
    
    return primes
}

print(displayPrimes(check))

Reference : Wikipedia