[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演算法
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
26

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. LinQ (Time Limit Exceeded)
1
2
3
4
5
6
7
8

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. Nomal - 硬幹(Time Limit Exceeded)
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
26

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. Nomal - 稍微聰明一點的硬幹(Time Limit Exceeded)
    由於可以知道只要是2的倍數絕對不會是質數,所以迴圈就直接i+=2了,殊不知還是Time Out…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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