wonseok.log wonseok.log

이 문제는 C++ 코드로 풀이를 작성하였습니다. 처음 이 문제에 접했을 때 소수 찾는 알고리즘은 이미 알고 있었습니다. 다음과 같은 알고리즘으로 풀이를 작성하였습니다. 하지만 다음과 같이 문제를 풀 경우 시간초과가 발생하게 됩니다. 시간복잡도를 계산해 봤을 때 O(n2)이라서 몇 개의 예외 케이스가 존재하게 됩니다. 이 문제를 시간복잡도를 줄이기 위해 수학적 지식을 사용하여 소수를 찾는 과정에서 2부터 루트n까지만 확인하면 됩니다. 이 방법의 시간 복잡도는 O(n루트(n)) 입니다. 답안 확인했을 때 모든 케이스에서 시간초과가 나지 않았습니다. 하지만 효율성 테스트에서 실패를 하게 되어 찾는 풀이를 알아 보니 소수 찾는 알고리즘에서 가장 시간 복잡도가 작은 알고리즘이 존재하였습니다. 에라토스테네스의 체 ..