herba   9달 전

코드는 이런데, 메모리가 딸린다... 이유는 ab범위 땜에 100조로 해둔 부분 같은데...내가 잘못 본 건가 하고  다시 봤는데도 100조...

hemisphere1357   9달 전

vector<bool>을 10^14개 선언하면 메모리 초과가 납니다.

대략 계산해봐도 10^14비트니까... 1TB를 가뿐히 넘습니다.

게다가 메모리가 해결된다고 가정해도 시간 초과가 날 가능성이 매우 큽니다.

ed가 10^14라고 한다면, 2부터 10^14라는 반복문 안에서 y*y부터 10^14까지 반복문을 돌리니 시간 초과가 납니다.

다른 방법을 생각해보셔야 할 듯합니다.

+) 17번째 줄에 arr[x] == 1은 대입 연산이 아닙니다. 비교 연산입니다. arr[x]에 1이 대입되지 않을 겁니다.

+) 16번째 줄에 10^14는 int로 받을 수 없습니다. 오버플로우가 일어납니다. 

wizardrabbit   9달 전

$A$, $B$의 범위가 말씀하신 대로 압도적이기 때문에 모든 값을 메모리에 담는 것만으로 메모리 초과가 발생할 것입니다.

조금 더 생각해 본다면 거의 소수의 정의는 소수의 제곱, 세제곱, 네제곱, ... 입니다. 소수를 제곱하는 것만으로도 수가 상당히 커지기 때문에 베이스가 되는 소수 범위는 의외로 꽤 제한됩니다. 베이스가 되는 소수들이 무엇이 될 수 있을지 떠올려보시면 좋을 것 같습니다.

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