[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演算法
  2. LinQ (Time Limit Exceeded)
  3. Nomal –  硬幹(Time Limit Exceeded)
  4. Nomal –  稍微聰明一點的硬幹(Time Limit Exceeded)
    由於可以知道只要是2的倍數絕對不會是質數,所以迴圈就直接i+=2了,殊不知還是Time Out…

參考:

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