[Swift] 백준 1978 - 소수찾기 (에라토스테네스의 체)

문제 링크

소수찾기 문제는 다양한 방법으로 풀 수 있다
가장 쉬운 방법은
2부터 해당숫자 전까지 모든 수로 나눠보는 것이다.
위 문제는 시간 제한이 길어서 이와 같이 풀이해도 괜찮다..!

풀이 코드

import Foundation

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

var count = 0

for i in nums {
    
    if i == 1 {
        count += 1
        continue
    }
    
    for j in 2..<i {
        if i%j == 0 {
            count += 1
            break
        }
    }
}

print(nums.count - count)

또는 해당 숫자의 제곱근까지만 계산해도 소수를 판별할 수 있다.

예를 들어
숫자 10인 경우 10 = 2 x 5 = 5 x 2 와 같이
모든 약수들은 대칭을 이루기 때문에
2까지만 확인해도 소수인지 아닌지 판별할 수 있다.

그러나 수가 더 많아지고 시간이 짧아지면 에라토스테네스의 체를 사용해야한다.

에라토스테네스의 체

1. 먼저 배열에 판별해야하는 수들을 다 넣어줍니다.
2. 2부터 자신의 배수가되는 숫자들을 모두 지워줍니다. (자신은 제외)
   • 예를 들어 숫자 2인 경우 : 4, 6, 8, 10 ...
   • 그 다음 3처리 : 6,9,12,15 ...
   • 만약 앞전에서 이미 지워졌다면 건너 뜁니다.
3. 2부터 시작하여 배열에서 지워진 숫자를 제외하고 모두 출력합니다.

이것을 코드로 구현하면

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

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 2...num {
    if numArray[i] != 0 {
        print(numArray[i], terminator: " ")
    }
}

• 이 코드는 num 범위 내의 소수를 출력하는 코드이다.

이 코드를 이용하여 위 문제를 풀어보면

풀이 코드

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)