题解 | #返回小于 N 的质数个数#

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
int main() {
    int n = 0,cnt = 0;
    scanf("%d",&n);
    bool *flag = (bool*)malloc(sizeof(bool) * n);
    int *pri = (int*)malloc(sizeof(int) * n);
    memset(flag,false,n);
    memset(pri,0,n + 1);
    for(int i = 2;i < n;i++)
    {
        if(!flag[i])
        {
            pri[++cnt] = i;
        }
        for(int j = 1;i * pri[j] < n;j++)
        {
            flag[i * pri[j]] = 1;
            if(i % pri[j] == 0)
            {
                break;
            }
        }
    }
    printf("%d",cnt);
    return 0;
}