[Swift] 백준 1929번 문제 소수 구하기

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

1929번: 소수 구하기

https://github.com/Ljunhyeob/baekjoon1929

GitHub - Ljunhyeob/baekjoon1929: 백준 - 1929

 

아래와 같이 했더니 메모리초과가 뜬다.... 시작하는 수부터 끝가지 반복문으로 나머지값을 비교해서 찾는거니 그럴만도 하다..

import Foundation

var value:[Int] = []
let num = readLine()!
let numArr = num.components(separatedBy: " ")
let a = Int(numArr[0])!
let b = Int(numArr[1])!

for i in a..<b{
    if i == 2 || i == 3{
        value.append(i)
    }else {
        for j in 2...a-1{
            if i % j == 0{
                
            }else {
                value.append(i)
            }
        }
    }
}
for i in 0..<value.count{
    print(value[i])
}

 

그래서 인터넷을 좀 찾아보니 에라토스테네스의 체 알고리즘 을 이용해야한다고 적혀있었다.

수학 못하는데 .. 뭐 간단하게 이해하고보니

n부터 m까지 의 범위안에서 소수를 구한다고 쳣을때

n~m 사이의 값이 저장되어있는 배열에 

2의배수를 빼고, 3의 배수를 빼고, 4의 배수를 빼고 ....... m-1 의 배수까지 빼는게 어라토스머시기 알고리즘 이라고 한다.

 

//
//  main.swift
//  baekjoon1929
//
//  Created by 이준협 on 2023/01/07.
//

import Foundation

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

let M = input[0]
let N = input[1]

var arr: [Int] = Array(repeating: 0, count: N + 1)
for i in 2...N {
    arr[i] = i
}

for j in 2...N {
    if arr[j] == 0 { continue }
    for k in stride(from: j + j, through: N, by: j) {
        arr[k] = 0
    }
}

for w in M...N {
    if arr[w] != 0 {
        print("\(arr[w])")
    }
}

그래서 위와같이 코딩을 하고 제출했더니 성공~