✅ 백준 문제 링크: 백준 1929번 - 소수 구하기1. 소수란? 소수(Prime Number)란 1과 자기 자신으로만 나누어 떨어지는 수를 의미합니다.즉, 약수가 1과 자기 자신뿐인 수를 소수라고 합니다. ✅ 소수 예시 (1~10까지)1, 2, 3, 4, 5, 6, 7, 8, 9, 10 → 소수: 2, 3, 5, 7 2. 소수 판별법 어떤 수 N이 소수인지 판별하는 기본적인 방법은1부터 N까지의 모든 수로 나누어보는 것이다. 그러나 이 방법은 시간 복잡도가 O(N) 이므로,입력값이 커질 경우 비효율적이다. ✅ 최적화된 소수 판별법 (제곱근 이용) 어떤 수 N이 소수인지 판별할 때,“N의 제곱근 이하의 수까지만 나누어 보면 충분” 하다.즉, sqrt(N) 이하의 수까지만 나눠보고 나누어 떨어지지 않으면 ..
