내 소식

나무다 [1151331] · MS 2022 · 쪽지

2026-04-11 00:47:52
조회수 71

이 논리가 은근 중요한 게

게시글 주소: https://orbi.kr/00078158546

양의 약수의 개수가 d(짝수)인 어떠한 수 n에서

sqrt(n) 이하의 n의 양의 약수의 개수는 d/2이다


이걸 확장하게 되는 일례로 소수 찾는 알고리즘이 되는데

에라토스테네스의 체(소수의 배수를 지우는 방식, O(nloglogn)를 쓰지 않고 

정해진 범위 n 내의 소수를 골라낼 때 sqrt(n)까지만 고려하면 됨 (자연수 k를 생각하면 2부터 k-1까지 다 나눠봄) 

그렇게 되면 시간복잡도가 O(n) -> O(sqrt(n))이 되면서 시간이 엄청나게 줄어듦

rare-최애의아이 아카네짱 rare-최애의아이 카나짱

0 XDK (+0)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.