exponential_e   5년 전

자바로 풀었구요, 일단 AC는 받았는데 대략 2000ms정도 나왔습니다.

제가 개념적으로아는 에라토스테네스의 체는, n = 2 이외의 2의 배수를 지우고, 그 다음 소수인 n = 3을 제외한 3의 배수를 지우고 ....

결국 n의 제곱이 구하려는 수보다 커질때까지 해당 배수를 지우는 기본 개념을 알고있습니다. 이를 코드로 구현 했을 때, 아래 제가 기입한 코드처럼 나오더라구요.

근데 시간이 짧게 나온분들 코드를 보니 저랑은 좀 다르게 코드를 짜셨던데, 제 코드의 허점이 있는거 같은데 어떻게 개선해야 할 지 잘 떠오르지가 않네요.ㅠㅠ

해당 코드의 비효율적인 면이 어떤건지 설명해 주실 수 있을까요.. (시간복잡도 상으로나..)

중간에 조건문이나 이런건 아직 안푸신 분들을 위해 최대한 배제하고 올립니다. 제 코드 채점 번호는 8535003번 입니다.

chogahui05   5년 전

안에 roo라는 변수를 두고 min = 1, max = 100만으로 두니

1.68억번 도네요. 느린 건 당연하지 않을까요?

chogahui05   5년 전

그래도 혹시 모르니. minuk씨가 작성한 코드의 시간 복잡도를 계산해 봅시다. 

일단 1부터 n까지 소수 목록을 쭉 뽑는다고 가정하면.


(1) x가 소수인 경우.

이 때 O(n-x)만큼 도네요.

(2) x가 소수가 아닌 경우.

continue

그러면 대충 소수 갯수에다가 n을 곱한 게 복잡도로 나올 텐데..

일단 sqrt까지 계산을 하므로, 루트(n)

그런데, 소수 정리에 의해서 1부터 q까지의 소수 갯수는 q/lnq에 근사함이 알려져 있습니다.

따라서 실제로 x가 소수인 event가 발생하는 경우는

root(n)/(ln(root(n)))

여기에 n을 곱하면.. 답 나오죠.

nroot(n) * 1/(ln(root(n)) 쯤 될 텐데요. 일단 100만에 루트를 씌우면 1000이고요.

nroot(n)을 구하면 대충 10억이네요.

그런데, ln(root(n)) = ln(1000)이므로 앞에 1/8 ~ 1/9가 곱해질 거에요.

chogahui05   5년 전

그런데 내부 for문을 for ( int j = i + i; j < INF; j += i )

이런 식으로 구성한 경우는 어떨까요?

이건 진짜로.. 루트 n만큼 안 돌고 그냥 n까지만 돌아도 minuk님 코드보다는 확실히 빠릅니다.

n(1+1/2+...+1/n) = nln(n)이기 때문에.. (아마.. 이게.. 1/x꼴 함수를 적분할 때 나오는 식일 겁니다. 막 lnx 나오고 그럴 테고요..)

기억은 안 나지만 샌드위치? 비슷한 정리로 잘 해 보면.. 1+1/2+...+1/n이 ln(n)으로 쳐도 된다는 걸 아실 수 있을.. 거에요.

핵심은. k로 떨어지는 것이냐를 검사하는데

Qk + r (단 0<r<k, Q>0, r,Q,k는 자연수) 가 k로 떨어지는지 검사할 필요가 없다는 겁니다.

exponential_e   5년 전

와 감사합니다.. 계산이 그렇게 되는거였군요.. 상위 분들의 코드랑 chogahui05님의 설명을 보니 어떤 차이인지 알거같습니다

에라토스테네스 체 관련한 코드나 설명을 더 찾아봐야겠어요 감사합니다!!

exponential_e   5년 전

아래의 추가적인 다른분들 코드 설명도 너무 감사합니다 ㅠㅠ 써주신 내용을 보니 어렴풋이 느껴졌던게 확 이해가되었네요 ㅎㅎ 감사합니다~

댓글을 작성하려면 로그인해야 합니다.