[BOJ] 백준 4134 다음 소수 (Swift)

문제

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

4134번: 다음 소수

풀이

n을 입력받은 후, n보다 크거나 같은 소수 중 가작 작은 소수를 출력해야합니다.
2부터 n - 1까지 나누어보고 나누어 떨어진다면 소수가 아니라고 판별할 수 있습니다.
이 방식은 $O(n)$의 시간 복잡도가 소요됩니다.

2부터 $\sqrt{n}$ 까지만 나누어 떨어지는지 확인해도 동일한 결과입니다.
이 방식은 $O(\sqrt{n})$의 시간 복잡도가 소요됩니다.
아래 포스팅에 정리를 해두었습니다.

https://dev-mandos.tistory.com/91

[알고리즘] 간단한 소수 판별 알고리즘 (Swift)

입력받은 n부터 시작하여 1씩 늘려서 n보다 크거나 같은 소수 중 가장 작은 소수를 구할 수 있습니다.

소스코드

	import Foundation
	func isPrimeNumber(num: Int) -> Bool {
	if num < 2 {
	return false
	}
	for i in 2..<Int(sqrt(Double(num)) + 1) {
	if num % i == 0 {
	return false
	}
	}
	return true
	}
	func solution() {
	var num = Int(readLine()!)!
	while !isPrimeNumber(num: num) {
	num += 1
	}
	print(num)
	}
	let t = Int(readLine()!)!
	for _ in 0..<t { solution() }

view raw 다음 소수.swift hosted with ❤ by GitHub

후기

효율적으로 소수를 판별하는 방법에 대해 알고있다면 쉽게 풀 수 있는 문제입니다.