204.计数质数

发表于 | 分类于
字数统计: 384 | 阅读时长 ≈ 1

一、题目描述

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

1
2
3
4
5
示例:

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

二、题解

1.算法描述

埃拉托斯特尼筛法

​ 埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

2.个人分析

​ 声明一个长度为n的数组，索引i作为待判断的数，索引中的值isPrime[i]作为该索引是否为素数的flag，使用for循环开始逐一判断数组索引i是否为素数，如果是素数，则将其n以内的所有倍数过滤，再判断下一个索引i。

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//爱式筛法
int countPrimes(int n)
{
    if (n < 2)
        return 0;
    int *isPrime = (int *)malloc(sizeof(int) * n);
    memset(isPrime, 0, sizeof(int) * n);//初始化isPrime为0
    int i, j, cnt = 0;
    for (i = 2; i < n; i++)
    {
        if (isPrime[i] == 0)
        {
            cnt++;
            for (j = i + i; j < n; j += i)
            { //筛去i的倍数
                isPrime[j] = 1;
            }
        }
    }
    return cnt;
}

三、PS:

void *memset(void *_Dst, int _Val, size_t _Size)

  • memset()函数为初始化一块连续的内存空间，按照字节赋值

  • _Dst：指针变量（起始位置）

  • _Val：初始化的值（一般为-1或0）
  • _Size：内存长度