[C#][LeetCode][Easy] 204. Count Primes

心得：

題目要求找出小於N(不包括N)的所有質數，由於N從3開始才會有質數(1非質數)所以直接回傳0，但是嘗試了很多方法都TimeOut，最後只好拜狗大神了。

最後找到了Eratosthenes演算法，小於等於根號N的所有質數去除N，若均無法整除則N為質數，有了這個觀念程式速度就快多了！

問題：

Count the number of prime numbers less than a non-negative number, n.

答案：

1. Eratosthenes演算法

   public class Solution {
       public int CountPrimes(int n) {
           if (n < 3) { return 0; }
   
           int count = 0;
           for (int i = 2; i < n; i++)
           {
               bool IsPrime = true;
               //開根號取最大值+1
               int sqrt = Convert.ToInt32(Math.Sqrt(i)) + 1;
               for (int j = 2; j <= sqrt; j++)
               {
                   if (i != j && i % j == 0)
                   {
                       IsPrime = false;
                       break;
                   }
               }
   
               if (IsPrime) { count++; }
           }
   
           return count;
       }
   }

2. LinQ (Time Limit Exceeded)

   public class Solution {
       public int CountPrimes(int n) {
           if(n < 3){ return 0; }
           var arr = Enumerable.Range(2, n);
           return arr.Count(x => x < n && !arr.Where(y => x > y).Any(y => x % y == 0));
       }
   }

3. Nomal –  硬幹(Time Limit Exceeded)

   public class Solution
   {
       public int CountPrimes(int n)
       {
           if (n < 3) { return 0; }
   
           int count = 0;
           for (int i = 2; i < n; i++)
           {
               bool IsPrime = true;
               for (int j = 2; j < i; j++)
               {
                   if (i % j == 0)
                   {
                       IsPrime = false;
                       break;
                   }
               }
   
               if (IsPrime) { count++; }
           }
   
           return count;
       }
   }

4. Nomal –  稍微聰明一點的硬幹(Time Limit Exceeded)
   由於可以知道只要是2的倍數絕對不會是質數，所以迴圈就直接i+=2了，殊不知還是Time Out…

   public class Solution {
       public int CountPrimes(int n) {
           if (n < 3) { return 0; }
   
           int count = 1;
           for (int i = 3; i < n; i += 2)
           {
               bool IsPrime = true;
               for (int j = 3; j < i; j += 2)
               {
                   if (i % j == 0)
                   {
                       IsPrime = false;
                       break;
                   }
               }
   
               if (IsPrime) { count++; }
           }
   
           return count;
       }
   }

參考：

1. https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/204md.html
2. [C#]輸出數字範圍內所有的質數