소수 구하기 소스...

다음 닷넷 카페에서 소수구하기 2~ 30000 내의 소수 구하기 타임어택을 해본다고 하기에... 나도 한번 해봤다

if와 continue가 소비시간을 그렇게 먹을줄 몰랐넹...

추가하면 할수록 느려지다뉭...

            long dt = DateTime.Now.Ticks;
            bool print = true;         
            for (short i = 2; i < 30000 ; i++){               
                for (short j = 2; j < i ; j++){
                    if (i % j == 0){
                        print = false;break;
                    }
                }
                if (print == true){
                    Console.WriteLine( i.ToString());
                }
                print = true;
            }
            TimeSpan ts = new TimeSpan(DateTime.Now.Ticks - dt);
            MessageBox.Show( ts.ToString() );

VS2005 , CPU : 쿼드 Q8300 , 램 : 4G, OS : XP

이게 가장 빠른 시간이   0.4218750 초이답...    0.4375000...
할때마다 다른데...
릴리즈로 하면 0.1초 빨라짐.

추가 : ...
워... 2~3만이 아니라 2부터 소수 3만개였다.
 3만개 띠웠더니 8초 좀 안되넹..

다른 방법을 찾아봤더니 제곱근 이용하는 방법이 있었다.


        //제곱근을 이용하여 체크. http://hisjournal.net/blog/128
        bool CheckByRoot(int num){
            int rootNum = (int)Math.Sqrt((double)num);
            int div = 0;
            bool value = false; 
            for(div = rootNum; num % div != 0; div--);  
            if(div == 1) value = true;
            else value = false;  
            return value;
            /*http://www.hackerschool.org/HS_Boards/zboard.php?id=Free_Board&no=8479
                "모든 정수는 대칭하는 두수의 곱으로 나타낼수 있다"의 특성을 이용해
                연산시간을 획기적으로 줄였습니다 -_-;;

                예를들어 18이란 정수는 1*18 2*9 3*6 6*3 9*2 18*1 로 나타낼수 있죠.
                여기서는 두 정수의 곱으로만 나타냈지만 실제로는 실수로도 가능합니다.
                3루트3 * 2루트3 로도 나타낼수 있죠.

                이처럼 대칭되어지는 두수의 곱으로 나타낼수 있기때문에 실제로 소수인지 확인
                하기위해서는 대칭되어지는 점[입력값의 루트값 즉 sqrt()함수를 이용한 결과값]
                까지만 연산을 해주면 된다는 결론이 나옵니다.

                그래서 두번째 방법에 하나의 변수를 더 추가하여[sqrt_number] sqrt값을 만들어
                내고 for문의 범위를 이 변수의 값까지로 한정시켰습니다.

                속도는....가히 눈부시군요 -_- 2번째 버젼에서 39초나 걸렸던 "1234567891" 란
                정수의 소수확인시 1초도 안걸립니다.....

                결론: 알고리즘이란게 재밌군요. 이제 다른 주제로 알고리즘 연구를 해봐야겠습니
                      다.

                */
        }

이거 적용해도 ... 그닥.. 0.0625초는 안나온다.

소인수분해를 이용해서 소스를 작성했으나...  실패했다.
이유인즉 소수를 찾기위해 수를 소수로 인수분해하려면 소수값을 가지고 있어야 하는데 꾀나 많은 소수들이 있어야 한다는... 벽에 부딪혔다. 30개를 가지고 131까지도 계산 못한다..

 int CheckBy(int num)
        {
            /*소인수분해 .
             
소인수분해를 할때는 가장 작은 소수부터 나누는게 좋습니다.

60을 소인수분해 한다고 하면,

60는 2의 배수죠? 그러면 2*30이 됨니다

그런데 30도 2의 배수죠? 그러면 2*2*15가 되죠..

15는 3의 배수입니다. 그러면 2*2*3*5

5는 소수이므로 더 이상 할 필요가 없습니다.

따라서 60을 소인수분해 하면 2²*3*5가 되는 것입니다

*/
            int[] primeNum = new int[] {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127};
            List<int> ar = new List<int>();
            int primeIndex = 0;
            int TempValue = 0;
            int modTempValue = 0;
            int primeCount = 0;
            TempValue = num;
            do
            {
               if( TempValue == 1 )
               {
                   ar.Add(TempValue);
                   break;
               }

               if (TempValue % primeNum[primeIndex] == 0)
               {
                   ar.Add(TempValue);
                   TempValue = TempValue / primeNum[primeIndex];
               }
               else
               {
                   primeIndex++;
               }
               
            } while (true); // 3개부터는 ~
            return ar.Count;
        }

줸장 ㅡ,.ㅡ;;


0.0625초는 대체 어떻게 나온거쥐?


실패했따 ㅡ.,ㅡ;;; 슬프다.. 



추가

카페에 갔더니 소스가 올라왔다... 봤더니 ~~ 와!! 대박!...
출력까지 포함시켜도 2초 정도 나온다.

제곱근과 소인수분해를 복합적으로 적용시켜놓은 소스였다... 

감탄뿐이 안나옴... 알고리즘 공부 좀 다시 해야겠다.