ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [펌] 10000000까지의 소수 표와, 구하는 프로그램의 속도를 높여보자.
    Programming 2007. 4. 16. 14:07
    반응형

    10000000까지의 소수는 직접 적어드릴수는 없습니다.

    10000000까지의 소수의 개수는 정확하게  664579개입니다.

    이 글에서는, 소수 구하는 프로그램 소스는 가르쳐 드리지 않습니다.

    중간중간에 써드리는 소스 만으로도 충분히 짜맞추실수 있기 때문이죠.

    소수 구하는 법을 아시는 분만 보시기 바랍니다.

    C++ 배우시는 분들이라면 소수 구하기는 80% 이상 해보셨을 겁니다.

    일반적으로, 100 정도밖에 안 구해 보셨을텐데요..

    그렇기 때문에 속도 차가 별로 나지가 않죠.

    하지만, 구하는 범위가 아주 넓어진다면 어떨까요??(이런.. 드라군 놀이가 생각나는걸..)

    시간차가 많이 날겁니다.

    죄송한 말씀이지만, C++를 처음 다루시는 분들이라면 정중히 뒤로 버튼을 누르라고 할께요.

    소수 구하는 프로그램을 짤때의 실수 유형을 봅시다!

    [1차원 배열을 사용해서 푸는 분들..]

    배열을 사용하는 방법은 작은 수에서는 상관이 없지만,

    10만이 넘어가는 경우에는 오류가 납니다.

    배열을 쓰시면 안되고, Check라는 변수를 만드세요!

    Check=0;

    if(i%j==0) Check=1;

    Check방을 0으로 초기화합니다. 그리고, i를 j로 나눕니다(꼭 i, j가 아니여도 됩니다.)

    그리고, i를 j로 나눴을대 나머지가 0이라면 결국 나누어 떨어진다는 말이므로,

    Check방을 1로 만듭니다. 그리고 그 아래부분에 이런 코드를 삽입해보죠.

    if(Check==1) break;

    한번이라도 나누어 떨어졌다면, 밖으로 튕겨 버리세요.

    (계속 해봤자 소수가 아니기 때문에 시간 낭비입니다.)

    그러면, 본격적으로 들어갑시다!

    [나누는 수를 몇까지 해야 할까?]

    일반적으로 소수는 에라토스테네스의 체 방법을 사용하죠.

    하지만, 이 방법은 시간이 조금 오래 걸린다는 단점이 있습니다.

    하지만, 가장 쉬운 방법이기도 하죠.

    쉽고, 빠르게 하는 방법이 있을까요?

    예! 있죠, 나누는 수의 범위를 바꿉시다.

    다음 코드를 볼까요?

     for(i=2;i<=10000000;i++){
      check=0;
      for(j=2;j<=i;j++){

    check방은 아까 설명 드렸을 겁니다. 초기화 시키는 것이죠.

    다중 for문을 사용했는데요, i 나누기 j 를 해서 값을 구할 것입니다.

    초보자 분들이시라면 저렇게 짜셨을 겁니다.

    그러면, for(j) 부분을 살펴 봅시다~!

    그 부분이 나누는 수 부분이 되겠지요.

    소수를 판별하려면 어디까지 다 나눠보아야 할까요?

    5라는 수가 있습니다. 일반적으로, 이 수가 소수인지 아닌지 판별하려면

    2부터 4까지 모두 나눠보게 되죠.

    (자기 자신과 1은 나누어 떨어지기 때문에 생략해야 합니다.)

    5÷2, 5÷3, 5÷4    <= 3번 계산을 하게 됩니다.

    물론, 3번 정도야 0.01초도 안걸리지만, 숫자가 무지하게 커진다면 어떨까요?

    저같은 경우는 1000만까지의 소수를 구해보려고 합니다.

    1000만개를 모두 나눠 보아야 할텐데, 언제 다 하겠습니까..

    그래서, 더 효과적인 방법을 찾아보자는 겁니다.

    1. for(j=2;j<=i/2;j++)

    이 방법은 아까 전보다는 시간을 2배 절약할 수 있습니다.

    이 방법도 정답이 틀리지는 않죠.

    왜냐하면, 어떤 수의 2분의 1보다  약수는 1개밖에(자기 자신) 없기 때문이죠.

    어떤 수의 2분의 1보다 큰 약수가 2개라면

    1개는 자기 자신이고, 나머지 1개는 어떤수의 2분의 1보다는 큰수.

    0

    정도로 식이 만들어지겠네요.

    j 의 값들 중에서, 자연수는 존재하지가 않기 때문에, 이렇게 해도 된다는 것입니다.

    하지만, 이것보다 효과적인 방법이 있을까요?

    예! 있습니다!

    바로, 그 수의 제곱근 까지만 구해보면 됩니다.

    이것은 제가 직접 증명은 못해드리지만, 적당히 해보시면 답이 똑같다는 것을 알수 있습니다.

    제곱근은  대략 √  요녀석을 말합니다.

    제곱근 함수를 쓰시려면, #include 로 하나를 더 불러와야 하는데요,

    math.h  를 불러와야 합니다.

    #include[math.h] 처럼요.

    [는 <로 바꿔주셔야 하는거 아시죠?

    sqrt(a)

    라고 쓰시면, a 의 제곱근이 구해집니다.

    그러면, 이렇게 변신하겠죠.

    for(j=2;j<=sqrt(i);j++){

    그러면 얼마나 속도가 향상될까요?

    제가 위의 세방법의 시간을 모두 재봤습니다.

    1번째 방법 : 측정 불가 (1시간 이상)

    2번째 방법 : 27분

    3번째 방법 : 1분 24초 -_-;;

    엄청난 차이가 있습니다.

    프로그래밍을 잘하려면 수학적 능력도 필요하다는 것을 절실히 느끼게 해주는 문제이네요.

    출처 : 네이버 지식인

    반응형

    댓글 2

    • Neon 2007.05.15 13:23

      한참 옛날 글에 리플 달아서 죄송합니다만, sqrt 함수가 얼마나 느린지를 생각해보시면, j<=sqrt(i) 대신에, j*j<=i 로 비교하시는게 훨씬 나을겁니다. 그리고, j를 1씩 iteration하는것보다 prime 값에 대해서만 iteration하는것이 훨씬 빠를 것입니다. vector<int> prime을 사용하세요. 대충 이정도까지 트윅을 하시면 E6400@3.2Ghz coLinux 환경에서 g++ -O2 -static 옵션으로 컴파일하는 경우에 2.6초 정도에 답이 나옵니다.(참 빠르죠? 낄낄낄)

    • Favicon of http://blmarket.net/tt BlogIcon Neon 2007.05.15 14:09

      윽... #icpc의 고수분들이 동일조건에서 0.06초가 걸리는 에라토스테네스의 체 기법을 제시하셨습니다. bit 노가다가 있어서 좀 복잡해요.

Copyright 2006-2021. Xeriars.com All rights reserved .