|
:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
08/09/07 01:06
for(i = Number; i>=2; i--)
for(j = 2; j<=Number/2; j++){ if(i%j==0) break; if(j == Number/2){ MaxPrimeNum = i; break; } if(MaxPrimeNum !=0) break; } 어줍잖게나마 완성했습니다만...전혀 깔끔하지 못합니다. 여기저기 break나 걸고 있으니...게다가 Int MAX_VALUE로 돌릴시에 꽤 많은 시간이 걸립니다.(약 17초 정도) 조금 더 좋은 개선방법 있거나 시간 단축을 줄일 수 있는 방법이 있으시면 많은 가르침 바라겠습니다.
08/09/07 01:14
bool is_prime(int a)
__int64 j; for(j=2; j*j<=a;j++) if(a%j==0) return false; return true; int max_prime(int Num) int i; for(i=Num;i>=1;i--) if(is_prime(i)) return i; return -1; 시간복잡도 O(N^1.5) 정도 될겁니다. 기본적인 아이디어는, 어떤 수 k가 소수인지 아닌지를 판별하는 데에는 2~[root(k)] 까지만 확인해보면 된다는 겁니다. 이 부분만 바꿔주셔도 시간은 무지막지하게 개선될 것으로 보입니다.
08/09/07 01:50
글쓴이께 궁금한점이 있습니다. 질게에서 최근 3일내에 같은 문제를 놓고 질문하신것으로 나오네요.
이 글들에는 친절하신분들이 댓글을 남겨 놓으셨구요. 그중에는 실제 소스를 올린분도 계십니다. 궁금해하시는 소수구하는 알고리즘의 최적화 버전에대해서 간단히 말씀하시기도 했구요. 그럼에도 불구하고 다시 질문을 올리시는 이유가 궁금합니다. 별다른 문제도 없이 말입니다. 이전의 글에 달린 댓글로도 충분히 많은것을 얻을수 있지 않았나요? 만약 스스로 해답을 찾기 원했다면, 다시 글을 올릴 이유가 없을 텐데요... 질문을 하시기 전에 이전 질문에 있던 댓글을 읽어보신것은 확실한가요?
08/09/07 02:33
tsana님// 말씀하시려는 뜻 잘 알겠습니다.
다만 중간중간 바꿔가는 과정에서 막히기 때문에 막히는 부분을 중점으로 질문 드렸던 것입니다. 제일 첫번째 문제는 제가 기존에 알고 있던 상식인 소수찾는데 n² 시간복잡도보다 줄이는 질문이고 두번째는 소스의 문제였고 세번쨰는 원래의 문제점을 거꾸로 돌려 찾다보니까 소스가 기이해져서 그것을 어느정도 깔끔하게 정리하고자 하여 질문 드린 것입니다.[공교롭게도 시간이 좀 많이 나온감이 있어서 그것에 대한 보강 질문을 했는데 첫번째 글에 있던 리플과 같은 답이 주어졌습니다. 지금보니까 어떤 원린지 이해가 되니 이건 제가 다시 꼼꼼히 살펴보지 못한 탓입니다.] 사실 알고리즘을 잡는게 많이 약한데다가 한동안 공부를 안해서 감이 떨어져 있기 때문에 어떻게든 할 수 있는 부분까지 해보고 그 이상 힘들것 같으면 이곳을 들려서 많은 분의 도움을 받을려하고 있습니다.
08/09/07 13:28
for (i=2;i<=N;i+=1)
if(pchk[i] == 0){/* 이 조건을 만족하면 i는 소수입니다. */ for(j = i*i; j<= N; j+=i){ pchk[j] = 1; } } 시간복잡도는 거의 선형시간이나 마찬가지입니다. 더 자세한 정보가 필요하시면 추가질문해주세요.
08/09/07 13:45
꿀호떡a님// 노노노, 질문자님의 기본 컨셉을 따라가면서 개선을 하는 방법이 더 멋져요. 꿀호떡a님의 답변이 질문자님의 성향에 잘 맞는 답인 듯 싶네요. ^^;
08/09/07 13:48
참고로 에라토스테네스의 체는 암호론 쪽이나 수학에 적용할 때를 제외하고는,
실용적인 측면에서는 상당히 유용합니다. 참고로 리만의 가설이 맞다는 전제 하에, Miller-Rabin Primality Test를 이용하시면 평균 O((log N)^5) 에 해결가능한 문제입니다.(큰 수부터 거꾸로 검사해주면 평균적으로 log N만에 소수를 찾을 수 있고, 테스트에 (log N)^4이 소요됩니다) sublinear time이고, 큰 소수(512비트라거나...)가 필요할 때 상당히 유용합니다.
|
||||||||||