[練習][C#] 質數計算

2011-06-04

9960
0
2011-06-04

[練習][C#] 質數計算

之前在討論區看到這種作業文的討論串，因為我平常都是在玩WinForm/WPF的功能實作，對於這種作業類型的練習沒乖乖寫過幾題，突然想該不會我的底子其實很糟糕吧！？於是今天就來實作看看吧。
解這種問題前我們必須先找出他的特性；
1.最小的質數是2。
2.除2以外的質數都是奇數。

之前在討論區看到這種作業文的討論串，因為我平常都是在玩WinForm/WPF的功能實作，對於這種作業類型的練習沒乖乖寫過幾題，突然想該不會我的底子其實很糟糕吧！？於是今天就來實作看看吧。

解這種問題前我們必須先找出它的主要特性：

1.最小的質數是2。
2.除2以外的質數都是奇數。
3.所有非質數都可做質因數分解。
4.非質數的最大質因數不會大於他的平方根。

其實這種問題大家都會解，問題就是出在效率而已。因此我打算示範兩次計算，其中一次不加上第四條的特性，等等我們來看看結果差多少。

    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch m_Stopwatch = new Stopwatch();
            m_Stopwatch.Start();

            for (int X = 0; X <= 1000000; X++)
            {
                //假設X是質數就將X存入m_Primes集合中以供下次查表使用。
                if (IsPrime(X))                    
                    m_Primes.Add(X);
            }

            m_Stopwatch.Stop();
            Console.WriteLine(m_Stopwatch.Elapsed);
            Console.ReadLine();
        }
        private static List m_Primes = new List();
        private static bool IsPrime(int number)
        {
            //第一條特性，如果數字小於二就立刻回傳false，表示此數不是質數。
            if (number < 2)
                return false;
            
            //這邊是實作第四條特性，為了不要讓迴圈每跑一次就計算一次平方根，我在這宣告一個欄位儲存起來。
            int maxValue = (int)Math.Sqrt(number);

            for (int curIndex = 0; curIndex < m_Primes.Count; curIndex++)
            {
                //這邊是第四條特性的重點，如果當前可能的質因數已經超過該數字的平方根，即表示這個數是一個質數，因此break離開迴圈。
                if (m_Primes[curIndex] > maxValue)
                    break;
                //第二條特性，假設這個數可以被m_Primes列表中的質數(0到目前為止所遇到的所有質數)整除，則這個數不是質數，回傳false。
                if (number % m_Primes[curIndex] == 0)
                    return false;
            }

            //所有無法證明其為非質數的數都是質數。
            return true;
        }
    }

我們來試試看計算1到100萬的質數有哪些。

第一次計算把第四條特性的實作拿掉來看看效能：

結果花費：

如圖所示，整個計算花費了34.32秒，或許你覺得蠻快了，畢竟1到100萬的質數也不少。

第二次計算把第四條特性實作的註解消除：

結果花費：

沒錯，你沒看錯我也沒有PO錯，原則上我是按下F5之後立刻就計算完成了。

程式語言好玩的地方或許就是這裡，僅僅兩條很簡單的程式碼就能在速度上提升一百多倍。

自學之路待續

回首頁