心得:
題目要求找出小於N(不包括N)的所有質數,由於N從3開始才會有質數(1非質數)所以直接回傳0,但是嘗試了很多方法都TimeOut,最後只好拜狗大神了。
最後找到了Eratosthenes演算法,小於等於根號N的所有質數去除N,若均無法整除則N為質數,有了這個觀念程式速度就快多了!
問題:
Count the number of prime numbers less than a non-negative number, n.
答案:
- Eratosthenes演算法
12345678910111213141516171819202122232425public 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;//開根號取最大值+1int 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;}} - LinQ (Time Limit Exceeded)
1234567public 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));}} - Nomal – 硬幹(Time Limit Exceeded)
12345678910111213141516171819202122232425public 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;}} - Nomal – 稍微聰明一點的硬幹(Time Limit Exceeded)
由於可以知道只要是2的倍數絕對不會是質數,所以迴圈就直接i+=2
了,殊不知還是Time Out…
1234567891011121314151617181920212223public 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;}}
參考: