心得：

題目要求找出小於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演算法
   
   C#

   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; } }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

   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)
   
   C#

   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)); } }

   1 2 3 4 5 6 7

   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)
   
   C#

   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; } }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

   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…
   
   C#

   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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   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#]輸出數字範圍內所有的質數