[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보다 크거나 같은 소수 중 가장 작은 소수를 구할 수 있습니다.

소스코드

후기

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