int is_prime(int num)
{
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0)
            return 0;
    }
    return 1;
}

int countPrimes(int n) {
    int ret = 0;
    for (int i = 2; i < n; i++)
        ret += is_prime(i);
    return ret;
}

// leetcode给的代码对数组的命名不对，这个数组应该为1时应该是合成数，为0时应该是质数
// 所以应该命名成 is_composite
static int *is_composite;

void get_composites(int n)
{
    for (int i = 2; i < n; ++i) {
        if (!is_composite[i]) {
            // n 不必被 2 ~ n-1 之间的每一个整数去除，只需被 2 ~ 根号 n 之间的每一个整数去除就可以了
            if ((long long)i * i < n) {
                // 应该直接从 i*i 开始标记，因为 2i,3i,… 这些数一定在 i 之前就被其他数的倍数标记过了
                for (int j = i * i; j < n; j += i) {
                    is_composite[j] = 1;
                }
            }
        }
    }
}

int is_prime(int n)
{
    return !is_composite[n];
}

int countPrimes(int n) {
    if (n < 2) {
        return 0;
    }
    is_composite = malloc(sizeof(int) * n);
    memset(is_composite, 0, sizeof(int) * n);
    get_composites(n);
    int ret = 0;
    for (int i = 2; i < n; i++)
        ret += is_prime(i);
    free(is_composite);
    return ret;
}

// leetcode给的代码里数组的命名不对，这个数组应该为1时应该是合成数，为0时应该是质数
// 所以应该命名成 is_composite
static int *is_composite;
static int *primes;
static int primes_size;

void get_primes(int n)
{
    for (int i = 2; i < n; i++) {
        if (!is_composite[i]) {
            primes[primes_size] = i; // 把新的质数插入数组
            primes_size++;
        }
        for (int j = 0; j < primes_size && i * primes[j] < n; j++) {
            // 只标记质数集合中的数与 i 相乘的数
            is_composite[i * primes[j]] = 1;
            // 如果 i 可以被 primes[j] 整除，那么对于合数 y = i * primes[j+1] 而言，
            // 它一定在后面遍历到 (i / primes[j] * primes[j+1]，这个数的时候会被标记，
            // 其他同理，这保证了每个合数只会被其「最小的质因数」筛去，即每个合数被标记一次。
            if (i % primes[j] == 0) {
                break; // 结束当前标记
            }
        }
    }
}

int is_prime(int n)
{
    return !is_composite[n];
}

int countPrimes(int n) {
    if (n < 2) {
        return 0;
    }
    is_composite = malloc(sizeof(int) * n);
    memset(is_composite, 0, sizeof(int) * n);
    primes = malloc(sizeof(int) * n); // 不用初始化为0
    primes_size = 0;
    get_primes(n);
    free(primes);
    free(is_composite);
    return primes_size;
}