이 논리가 은근 중요한 게

Question

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

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

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

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

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

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

세계의야마다 · Accepted Answer

images

OKASHII · Answer

양의 약수의 개수 짝수까지 이해했습니다

Le petit prince · Answer

자자자이제 소수계량함수가 x/lnx로 근사된다는 사실을 증명해보자

JFamily&목동의현자(우리) · Answer

수학공식 코딩에 적용하는것 좋은것가틈
근데 그건 수학교수님들한테 외주드리면 됨

최근 게시글 · 더보기