[Programmers] Lv1. 소수 찾기

• 이 문제는 C++ 코드로 풀이를 작성하였습니다.

---

처음 이 문제에 접했을 때 소수 찾는 알고리즘은 이미 알고 있었습니다.
다음과 같은 알고리즘으로 풀이를 작성하였습니다.

하지만 다음과 같이 문제를 풀 경우 시간초과가 발생하게 됩니다.
시간복잡도를 계산해 봤을 때 O(n2)이라서 몇 개의 예외 케이스가 존재하게 됩니다.


이 문제를 시간복잡도를 줄이기 위해 수학적 지식을 사용하여 소수를 찾는 과정에서
2부터 루트n까지만 확인하면 됩니다.

이 방법의 시간 복잡도는 O(n루트(n)) 입니다. 답안 확인했을 때 모든 케이스에서 시간초과가 나지 않았습니다.
하지만 효율성 테스트에서 실패를 하게 되어 찾는 풀이를 알아 보니 소수 찾는 알고리즘에서 가장
시간 복잡도가 작은 알고리즘이 존재하였습니다.

---

에라토스테네스의 체

2부터 시작해 2의 배수를 다 제거하고 그 다음 소수인 3을 찾아 3의 배수를 제거하는 방식의 알고리즘입니다.

이 방법의 시간 복잡도는 O(log(logn))이라고 합니다.

- 혹시 궁금한 점이나 수정할 사항 있으면 댓글로 남겨주세요.