|
:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
08/09/05 22:07
n까지의 경우
n개의 flag를 만들어서 2부터 n/2까지 루프 돌려서 배수 플래그에 off해주면 on중에 가장 큰수가 답이 될것 같습니다. 생각해보니 이방법도 큰 수 앞에서는 무력할것 같네요... ps. 루프 돌면서 off된 수는 배수처리 안해도 되고 on된 수만 해도 되겠네요
08/09/05 22:46
소수체크는 2부터 루트x까지만 해주면 됩니다.
답이 구간의 뒷부분에 있을걸로 예상되므로 루프 거꾸로 돌리면 시간복잡도가 n루트n보다 더 작은 정도가 되겠네요 O(n)의 방법이 있는지 정말 궁금하네요
08/09/05 23:17
뒤에서부터 돌린다면, 금방 찾겠죠. 수가 충분히 클 때, 소수 p 와 인접한 소수와의 거리(간격)은 대략 log p 정도라는 게 정수론에서 알려진 내용 중 하나인데..
N이 충분히 크다고 하면 N 이하의 최대 소수 P에 대하여 N≒P 이므로(?), 소수 검사에 드는 시간복잡도가 O(sqrt N) 라면 기대값으로 O(logN * sqrtN) 정도 되네요~ N이 12자리면 logN은 약 40~50 근처고(반복 횟수가) 실제로는 소수 검사할 때 커팅이 금방금방 되므로, 되게 빨리 나옵니다. 지금 막 짜봤는데 왠만한 64bit integer 까지는 금방 나오네요-_a 1초도 훨씬 안되는...... 사실 sqrtN 의 시간복잡도보다 더 빠른 소수 검사 알고리즘이 존재합니다. 관심이 있으시면 찾아보세요-_-a 아직도 알고리즘 분야에서 많이 연구되고 있는 것 중 하나고, N이 어떤 특정 수 이하라는 조건만 있으면 (주로 실용적으로 쓰는 32bit 나 64bit에 대한 조건들) 매우 빠르게 동작합니다. 소스 첨부합니다. #include <stdio.h> bool isprime(__int64 p) __int64 i; if(p & 1) return 0; for(i=3; i*i<=p; i+=2) { if(p % i == 0) return 0; return true; } int main() __int64 n = 100000003500600; for(__int64 p = n-1; p>=0; --p) { if( isprime(p) ) { printf("%I64d\n", p); break; } return 0; }
08/09/05 23:22
덧 : 위의 isprime 함수는 완전하지 않습니다 [....] 1이나 2, 3, ... 등 아주 작은 special case 에 대해서는 조금 틀린데-_-; 문제에서 찾는 수가 엄청 크다는 조건 하에 대충 저렇게 적었습니다. 엄밀성을 위해서는 예외처리도 해주세요~
08/09/05 23:23
2002년도 즈음에 linear time에 소수 찾는 알고리즘이 발표되었던 걸로 기억하는데, 그 자료를 다시 찾아보려니까 잘 안 찾아지네요..
다익스트라 교수 타계 즈음이라 시기가 대충 기억나는데...
|
||||||||||