알고리즘 - 에라스토스테네스 체(소수찾기)[Swift]

에라스토스테네스 체

소수를 찾는 알고리즘이다.

0 ~ 3000 범위의 소수를 찾는다고 할경우 n = 3000이 된다.

우선 n+1개의 불리언 배열을 생성해야 한다. n개를 생성할 경우 0을 포함하기 때문에 2999까지 만들어져서 인덱스를 벗어나게된다.

만약 자기 자신이 이미 false처리 되었다고 하면 pass를 하게되고

아닐 경우 i + i ~ n+1 까지 i씩 증가하면서 i의 배수(소수가 아닌 수)의 인덱스를 false 처리 하게된다

 

소스코드

let n = 3000
var isPrime = [Bool](repeating: true, count: n+1)
//0과 1은 소수가 아니다.
isPrime[0] = false
isPrime[1] = false

for i in 0...n{
	for j in stride(from: i+i, to: n+1, by: i){
        isPrime[j] = false
    }
}