알고리즘 톺아보기 (1) 썸네일형 리스트형 소수 찾기에서 제곱근을 사용하는 이유 제곱근을 이용한 소수 찾기 알고리즘소수(Prime Number)는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수이다.소수를 찾는 알고리즘은 수학적 계산의 핵심 요소 중 하나로, 효율성을 높이는 것이 중요하다.이번 포스팅에서는 소수 찾기 문제에서 검사할 수의 제곱근을 사용하는 이유와,이를 통해 시간 복잡도를 줄인 코드 구현에 대해 소개하려한다.소수 판별의 기본 원리소수를 판별하기 위해 가장 단순한 방법은 주어진 수 n에 대해2부터 n-1까지의 모든 수로 나누어 나머지가 0이 되는지 확인하는 것이다.하지만 이 방법은 매우 비효율적이며, 시간 복잡도는 O(n)이다.제곱근을 활용한 소수 판별법소수 판별에서 검사할 수의 제곱근을 사용하면시간 복잡도를 O(√n)으로 줄일 수 있다.이는 수학적 원리에서 비롯된다.. 이전 1 다음