Count Primes，countprimes

Count Primes，countprimes

examination questions

Description:

Count the number of prime numbers less than a non-negative number, n

How Many Primes Are There?

Sieve of Eratosthenes

Please use the following function to solve the problem：

int countPrimes(int n){

}

解題代碼

int countPrimes(int n) {
    if (n == 0 || n == 1 || n == 2){
        return 0;
    }
    if (n == 3){
        return 1;
    }

    int temp = 0;
    bool flag = false;
    int arr[200] = { '\0' };
    int k = 0;
    arr[0] = 2;

    for (int i = 3; i < n; i++){
        for (int j = 0; j <= k; j++){
            if (i%arr[j] == 0){
                flag = true;
                break;
            }
        }

        if (flag == false){
            if (k < 199){
                k++;
                arr[k] = i;
　　　　　　　　　 i++; 
            }
            temp++;
        }
        else{
            flag = false;
        }
    }

    return temp+1;
}

基本算法思想

判斷一個數是否是質數, 僅需判斷這個數是否能被比這個數小的質數整除, 若不能, 就是質數.

代碼注釋分析

int countPrimes(int n) {
    //題目要求輸入的測試值是非負數,所以必須包含0,1的特殊情況
    //由於2的結果也是0,所以也包含了進去
    if (n == 0 || n == 1 || n == 2){
        return 0;
    }
    //為了方便後面的算法設計,要單獨把3拿出來
    if (n == 3){
        return 1;
    }

    int temp = 0;//定義一個計數器,用來記有多少個質數
    bool flag = false;//標記,用來判斷該數是否是質數
    int arr[200] = { '\0' };//最為基數的質數的量的最大值設置為200,可以測試10的6次方量級
    int k = 0;//用來計數質數的個數的,也就是arr的下標
    arr[0] = 2;//第一個質數賦值為2

    for (int i = 3; i < n; i++){ //這個循環符合n>=4的情況,遍歷所有小於n的數,一一進行檢測
        for (int j = 0; j <= k; j++){ //如果這個數能被arr[0]~arr[k]整除,說明它不是質數,flag變為true
            if (i%arr[j] == 0){
                flag = true;
                break;
            }
        }

        if (flag == false){ //如果flag沒有變成true,那麼說明它是質數
            if (k < 199){ //我們要求arr質數僅需要200個,超出的不計入!
                k++; 
                arr[k] = i; //把這個質數也加入arr數組中
                i++;//一個質數被判斷為質數後,它的後面一個數字不可能是質數(除了2和3之外),所以用i++來減少對不不要數的檢測
            }
            temp++; //質數量+1
        }
        else{
            flag = false; //把flag 再初始化為false,回到最初狀態,用於判斷下一個數值
        }
    }

    return temp + 1;//+1是因為要加上 2 這個質數,上面的temp中不包括2
}

此外, 有以下解題方法供參考(由 stevenczp 提供):

int countPrimes(int n) {
bool* map = (bool*)malloc(n * sizeof(bool));
memset(map, 0, n * sizeof(bool));

for (int i = 2; i <= sqrt(n); i++)
{
if (map[i])
continue;
int t = 2 * i;
while (t < n)
{
map[t] = true;
t += i;
}
}

int result = 0;
for (int i = 2; i < n; i++)
{
if (!map[i])
result++;
}
return result;
}

關於本題的詳細解題過程, 請點擊這裡:

解決一道leetcode算法題的曲折過程及引發的思考