알고리즘 - 소수 판별법 알고리즘

방법1: 제곱근

 

만약 N이 12라고 할 때 N의 제곱근은 약 3.46이다. 

그리고 12의 약수는 1,2,3,4,6,12 이다. 

1과 12를 제외하고는 2*6, 3*4, 4*3, 6*2이다.

2*6, 3*4, 4*3, 6*2의 관계는 몫이 커지면 나누는 값이 작아지거나 값이 커지면 몫이 작아지는 반비례 관계이다. 

결국 N의 제곱근까지 향하게 되면 이후 몫과 나누는 값이 반대로 바뀌게만 되는 상황이다.

 

-> 따라서 N의 제곱근까지 나누어 떨어지는 여부를 조사하면 소수 판별이 가능하다.

 

 

알고리즘

1. 1은 소수가 아니므로 먼저 처리

2. 짝수는 소수가 아니므로 false처리

3. 2 ~ N 제곱근까지 나눠본 후 하나라도 나눠 떨어지는 것이 존재하면 false

4. N제곱근까지 나눴음에도 나눠떨어지지 않는 경우 소수

 

시간복잡도: O(sqrt(n))

-> N이 커지면 소수를 판별하는데 시간이 오래 걸림

 

---

방법2: 에라토스테네스의 체

-> 소수의 개수 또는 소수들을 구하는 방법 중에서 가장 보편적으로 이용되는 방법.

 

초기값이 0인 N개의 원소를 갖는 배열을 선언하여, 소수가 아닌 수는 체크해주는 방식이다.

 

소수(x)의 배수는 약수로 무조건 x를 포함하게 된다.

따라서 절대 소수의 배수는 소수가 될 수 없다. 이를 이용한 것이 에라토스테네스의 체이다.

가장 작은 소수인 2부터 시작해, 2의 배수를 다 지웠으면, 지워지지 않은 수 중에서 다음 값인 3의 배수를 지워나가고 이를 계속해서 반복해 나가면 소수만 남게 된다.

 

알고리즘

1. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
2. 자기 자신을 제외한 2의 배수를 모두 지운다.
3. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
4. 자기 자신을 제외한 3의 배수를 모두 지운다.
5. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
6. 자기 자신을 제외한 5의 배수를 모두 지운다.
7. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
8. 자기 자신을 제외한 7의 배수를 모두 지운다.
9. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

120은 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다

 

코드 

import Foundation

let testCase = Int(readLine()!)!
let nums = readLine()!.split(separator: " ").map{Int(String($0))!}

var num = 1000
var numArray = Array(repeating: 0, count: num + 1)
var count = 0

for i in 2...num {
    numArray[i] = i
}

for i in 2...num {
    if numArray[i] == 0 {
        continue
    }
    
    for j in stride(from: i+i, through: num, by: i) {
        numArray[j] = 0;
    }
}

for i in nums {

    if numArray.contains(i) {
        count += 1
    }
}

print(count)

 

 

시간/공간 복잡도

• 시간복잡도: O(nloglogn)

 

 

참고: https://jm-park.github.io/algorithm/2018/08/06/Prime-Number(%EC%86%8C%EC%88%98)-%ED%8C%90%EB%B3%84%EB%B2%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.html