[数据结构与算法]计数质数 C语言（LeetCode--204）

有问必答（评论区见）

统计所有小于非负整数?n?的质数的数量。

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

方法一：暴力算法

双循环从2到n逐个判断

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int i=2,n;
    int count=0;
    int flag=1;
    printf("n=");
    scanf("%d",&n);
    if(n<2)
        printf("%d",count);
    else
    {
        while (i<n)
    {
            for (int j = 2; j <i ; j++)
        {
               if(i%j==0)
            {
                flag=0;
                break;
            }
        }
        if(flag)
        {
            count++;
        }
        flag=1;
        i++;
    }
    printf("%d",count);
    }
    return 0;
}

方法二：厄拉多塞筛法

原理见厄拉多塞筛法_学如逆水行舟，不进则退-CSDN博客_厄拉多塞筛法

1、常规版

从2到根号n

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
    int n;
    scanf("%d",&n);
    int *isprime=malloc(sizeof(int)*n);
    for(int i=0;i<n;i++)
        isprime[i]=1;
    for(int i=2;i<sqrt(n);i++)
    {
        if(isprime[i])
        {
            int k=2;
            while(k*i<n)
            {
                isprime[k*i]=0;
                k++;
            }
        }
    }
    int count=0;
    for(int i=2;i<n;i++)
    count+=isprime[i];
    printf("%d",count);

}

进阶版

直接跳过2的倍数，从3开始

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
    int n;
    scanf("%d",&n);
    int count=n>2?1:0;
    int i,j,k;
    int *isprime=malloc(sizeof(int)*n);
    for(int i=0;i<n;i++)
        isprime[i]=1;

    for(i=3;i<n;i+=2)
    {
        if(isprime[i])
        {
            count++;
            if(i<sqrt(n))
            {
                for(j=i;i*j<n;j+=2)
                {
                    k=i*j;
                    isprime[k]=0;
                }
            }
        }

    }
    printf("%d",count);

}