[알고리즘] 에라토스테네스의 체

contents

에라토스테네스의 체

소수 판별 알고리즘으로 대량의 소수 판별이 필요할 경우 사용합니다.

소수 판별 방식

2부터 판별 수 전까지 for문 돌리는 방식 → O(n)O(n)O(n)

func isPrime(_ num: Int) -> Bool {
    guard num > 1 else { return false }

    for i in 2...num {
        if num % i == 0 { return false }
    }

    return true
}
Swift
복사

해당 숫자의 절반까지 for문 돌리는 방식 → O(n)O(n)O(n)

func isPrime(_ num: Int) -> Bool {
    guard num > 1 else { return false }

    for i in 2...num/2 {
        if num % i == 0 { return false }
    }

    return true
}
Swift
복사

2부터 n\sqrt{n}n​ 까지 for문 돌리는 방식 → O(n)O(\sqrt{n})O(n​)

func isPrime(_ num: Int) -> Bool {
    guard num > 1 else { return false }

    for i in 2...num where i * i <= num  {
        if num % i == 0 { return false }
    }

    return true
}
Swift
복사

대량의 소수 판별

원리

⓵ 소수를 판별할 범위만큼 배열 할당, 값 넣기

var arr = Array(repeating: 1, count: m+1)
Swift
복사

⓶ 2부터 특정 수의 배수에 해당하는 수를 모두 지우기 → 자기자신은 지우지 않고 이미 지워진 값은 넘어감

for i in 2...m {
    if arr[i] == 1 {
        for j in stride(from: i+i, to: m+1, by: i) {
            arr[j] = 0
        }
    }
}
Swift
복사

⓷ 남은 수 출력하기

for i in n...m {
    if arr[i] == 1 { print(i) }
}
Swift
복사

예제 풀이

1929. 소수 구하기

1929번: 소수 구하기

https://www.acmicpc.net/problem/1929

let nm = readLine()!.split(separator: " ").map{ Int(String($0))! }
let n = nm[0]
let m = nm[1]

var arr = Array(repeating: 1, count: m+1)
arr[0] = 0
arr[1] = 0
for i in 2...m{
    if arr[i] == 1{
        for j in stride(from: i+i, to: m+1, by: i) {
            arr[j] = 0
        }
    }
}

for i in n...m{
    if arr[i] == 1 { print(i)}
}
Swift
복사

4948.

베르트랑 공준

4948번: 베르트랑 공준

https://www.acmicpc.net/problem/4948

var arr = Array(repeating: true, count: 246913)

for i in 2...246912 {
    if arr[i] == true {
        for j in stride(from: i*i, through: 246913, by: i) {
            arr[j] = false
        }
    }
}

while true {
    var n = Int(readLine()!)!
    var sum = 0

    if n == 0 {
        break
    }

    for i in n+1...n*2 {
        if arr[i] {
            sum += 1
        }
    }
    print(sum)
}
Swift
복사