LeetCode#204 Count Primes

2018-09-10
#LeetCode #C #Prime
程式解題/ LeetCode

問題

經典問題，給一個非負整數 n ，問小於 n 的質數有幾個。

輸入與輸出

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

方法

建質數表。

方法一： 逐一檢查 1 ~ n - 1 的整數中有多少個質數，但效率不好，因此採用第二種方法。

方法二： 埃拉托斯特尼篩法，從 2 開始將已知質數的倍數標記成合數，可以減少很多不必要的計算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int countPrimes(int n)
{
    int i, j, prime_count = 0;
    bool* primes = malloc(n * sizeof(bool));
    memset(primes, true, n * sizeof(bool)); 

    for (i = 2; i < n; i++)
    {
        if (primes[i])
        {
            prime_count++;
            for (j = 2 * i; j < n; j += i)
                primes[j] = false;
        }
    }

    return prime_count;
}