이번 글에서는 소수 판정에 대한 개념과 코딩 테스트에서 소수 판정 문제를 해결하는 방법에 대해 알아보겠습니다. 소수는 많은 알고리즘 문제에서 자주 등장하는 중요한 주제 중 하나이므로, 이 글을 통해 여러분의 코딩 실력을 향상시킬 수 있기를 바랍니다. 소수의 개념 소수는 1과 자기 자신만으로 나누어 떨어지는 수입니다. 예를 들어, 2, 3, 5, 7은 모두 소수입니다. 반면에 4, 6, 8은 다른 수로도 나누어지므로 소수가 아닙니다. 코딩 테스트에서의 소수 판정 문제 접근 방법 가장 간단하고 직관적인 방법으로는 대상 숫자 n을 [2, √n] 범위의 모든 수로 나눠보는 것입니다. 만약 어떤 수 i로 n이 나누어진다면 n은 소수가 아닙니다. 이 방법은 시간 복잡도 O(√n)으로 비교적 간단하게 구현할 수 있습..
