---
title: 'LeetCode 204. Count Primes'
disqus: hackmd
---

# LeetCode 204. Count Primes

## Description

Given an integer n, return the number of prime numbers that are strictly less than n.

## Example

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

## Constraints

0 <= n <= 5 * 10^6^

## Answer

此題取2~n去算有幾個質數，可以一個一個取出，然後用while loop檢查其有無因數，若無就cnt++，此解可行，但所需時間太久。

int countPrimes(int n){
    int i = 2, j = 2, tmp = 0, flag = 1, cnt = 0;
    while(i<n){
        flag = 1;
        j = 2;
        tmp = sqrt(i);
        while(flag && j<=tmp){
            if(i%j == 0){flag = 0;}
            else{j++;}
        }
        if(flag){cnt++;}
        i = i&1 ? i+2 : i+1;
    }
    return cnt;
}

我們可用hash table的方式來做紀錄，有個規律是從每個數i的次方開始，每疊加i就都不是質數，因其有i為因數。比如從3^2^開始每加3為12、15、18...都不為質數，因其都有3為因數。所以依照此概念，我們可將小於n的非質數都挑出，最後只要計算有幾個即可。

int countPrimes(int n){
    int i = 2, j = 2, k = 2, cnt = 0, tmp = 0;
    int *tab = (int*)malloc(sizeof(int)*n);
    for(i = 0; i<n; i++){tab[i] = 1;}
    tmp = j*j;
    while(tmp<n){
        if(tab[tmp]){
            while(tmp<n){
                tab[tmp] = 0;
                tmp += j;
            }
        }
        j = j&1 ? j+=2 : j+1;
        tmp = j*j;
    }
    while(k<n){
        if(tab[k]){cnt++;}
        k = k&1 ? k+2 : k+1;
    }
    free(tab);
    return cnt;
}

## Link
https://leetcode.com/problems/count-primes/
###### tags: `Leetcode`