随着计算机技术和算法的发展，计算素数个数的方法也不断得到改进。其中，C++ 作为一门高效的编程语言，可以很好地实现求解素数个数的功能。本文将介绍 C++ 中几种常见的统计素数个数的方法。

1. 埃拉托斯特尼筛法（Sieve of Eratosthenes）

埃拉托斯特尼筛法是一种简单而高效的算法，它的思路是：从小到大枚举每个数，把它的倍数全部标记为合数，直到最后只剩下素数。具体实现可以用一个布尔数组来表示每个数是否被筛掉，最后统计未被筛掉的素数个数即可。

以下是使用埃拉托斯特尼筛法实现统计素数个数的示例代码：

 C++
int countPrimes(int n) {
  vector<bool> isPrime(n, true); // 初始化所有数为素数
  for (int i = 2; i * i < n; i++) {
    if (!isPrime[i]) continue; // 已经被筛掉了，跳过
    for (int j = i * i; j < n; j += i) {
      isPrime[j] = false; // 标记为合数
    }
  }
  int count = 0;
  for (int i = 2; i < n; i++) {
    if (isPrime[i]) count++; // 统计未被筛掉的素数个数
  }
  return count;
}

2. 线性筛法（Linear Sieve）

线性筛法是对埃拉托斯特尼筛法的优化，它的核心思想是每个合数只被它的最小质因子筛掉一次。具体实现中，从小到大枚举每个数时，除去它的最小质因子后所得到的数为合数，但是由于它已经被它的最小质因子筛掉过了，所以不需要再重复标记。

以下是使用线性筛法实现统计素数个数的示例代码：

 C++
int countPrimes(int n) {
  vector<int> primes; // 存储所有素数
  vector<int> isPrime(n, true); // 初始化所有数为素数
  for (int i = 2; i < n; i++) {
    if (isPrime[i]) {
      primes.push_back(i); // 添加素数到列表中
    }
    for (int j = 0; j < primes.size() && i * primes[j] < n; j++) {
      isPrime[i * primes[j]] = false; // 标记合数
      if (i % primes[j] == 0) break; // 跳出循环，保证每个合数只被它的最小质因子筛掉一次
    }
  }
  return primes.size();
}

3. 埃式筛法（Sieve of Atkin）

埃式筛法是一种比较新的素数筛法，它利用数学方法来筛选素数。其基本原理是找到一些模式，通过计算它们的生成公式、判别式、精度控制等方式，对素数和合数进行快速的判断和区分。

以下是使用埃式筛法实现统计素数个数的示例代码：

 C++
int countPrimes(int n) {
  if (n <= 2) return 0;
  if (n <= 3) return 1;
  vector<bool> isPrime(n, false); // 初始化所有数为合数
  int sqrt_n = int(sqrt(n));
  for (int i = 1; i <= sqrt_n; i++) {
    for (int j = 1; j <= sqrt_n; j++) {
      int num = 4*i*i + j*j;
      if (num <= n && (num % 12 == 1 || num % 12 == 5)) {
        isPrime[num] = !isPrime[num];
      }
      num = 3*i*i + j*j;
      if (num <= n && num % 12 == 7) {
        isPrime[num] = !isPrime[num];
      }
      num = 3*i*i - j*j;
      if (i > j && num <= n && num % 12 == 11) {
        isPrime[num] = !isPrime[num];
      }
    }
  }
  int count = 0;
  for (int i = 5; i < n; i++) {
    if (isPrime[i]) count++; // 统计未被筛掉的素数个数
  }
  return count + 2; // 加上 2 和 3 两个素数
}

总结：

本文介绍了 C++ 中三种常用的统计素数个数的方法，分别是埃拉托斯特尼筛法、线性筛法和埃式筛法。不同方法之间的时间复杂度和实现难度存在一定的差异，选择合适的方法可以提高计算效率。

相似文章
• 《C++通讯录课程设计报告》
  在本学期的程序设计课程中，我们学习了C++的基础语法和相关编程技能，对于这门课程的主要目的是实现一个通讯录管理系统，利用所学知识进行开发，最终完成一个高效、用户友好的软件。在此，我将就此课程的设计过程展开报告。
  
  
• C++动态调用类简介
  C++是一门广泛应用的编程语言，非常适合用于开发大型项目。其中一个关键的特性就是它的面向对象编程（OOP）能力。在C++中，我们可以使用类（class）创建对象，实现代码复用和抽象。C++还支持动态链接库（DLL）和运行时类型信息（RTTI
  
  
• C++访问数据库是否必要？
  C++是一种常用的编程语言，广泛应用于软件开发、游戏开发、嵌入式系统等领域。而数据库是存储和管理数据的重要工具，是许多应用程序必不可少的组成部分。那么C++访问数据库是否必要呢？
  
  
• 如何解决visual c++ 6.0打不开的问题？
  Visual
  
  
• C++函数实现最大公约数和最小公倍数的计算
  C++是一种快速高效的编程语言，也是许多开发人员的首选。C++可以帮助您实现最大公约数和最小公倍数的计算。在这篇文章中，我们将了解如何使用C++函数来编写代码以执行这些计算。
  
  
• 如何在C++中不使用strcat而使用循环连接两个字符串？
  在C++中，字符串连接是一个很常见的操作。通常使用函数strcat()可以很轻松地完成字符串连接。然而，有时候我们会有不得已的情况，需要在C++中不使用strcat()函数进行连接，而是使用循环来连接两个字符串。
  
  
• C++实现线性表：基础数据结构的学习指南
  C++是一种强大的编程语言，被广泛用于计算机科学中的基本数据结构和算法。在数据结构中，线性表是一种基本的数据结构之一。线性表是以线性序列的方式存储和管理数据的特定集合。它们是由一系列节点组成的，每个节点都包含一个值和指向下一个节点的指针。C
  
  
• C++类模板的模板参数列表：如何使用？
  C++是一种广泛使用的编程语言，它的一大特点就是支持类模板的使用。类模板是一种通用代码设计技术，它可以使程序员编写可用于各种数据类型的代码。在使用C++类模板时，需要使用模板参数列表来指定模板参数。
  
  
• C++ 的 abort() 函数
  在C++编程语言中，abort()函数是一种用于终止程序的函数。它可以在程序运行过程中被调用，以实现一种无条件的终止程序的方式。
  
  
• C++合法的字符常量规则详解
  在C++中，字符常量是由一对单引号
  
  
• C++多线程 编程技术详解
  C++多线程编程技术详解
  
  
• C++如何清空二维数组
  二维数组是一个非常实用的数据结构，它可以存储多行多列的数据。在使用C++的过程中，我们经常需要清空二维数组，以便在其它地方重复利用它。
  
  
• 使用二进制在C++中保存数据
  在计算机科学中，二进制是一种非常重要的数字系统。由于计算机只能理解二进制，因此许多程序员使用C++来存储和处理数据时使用二进制。在本文中，我们将探讨如何使用C++将数据保存为二进制。
  
  
• C++编写游戏脚本是否会被检测？
  在游戏开发中，人们经常使用程序脚本来控制游戏中的逻辑和事件。C++是一种常用的编程语言，许多游戏开发者使用它来编写游戏脚本。然而，许多游戏公司和游戏平台都有反作弊机制，这使得许多玩家担心，他们使用C++编写的游戏脚本是否会被检测。
  
  
• C++中的/=有什么意义？
  在C++中，/=是一个复合赋值运算符，它与其他常用的赋值运算符如=、+=、-=和*=等一样有效。它用于将一个变量或表达式除以另一个值，并将结果赋给变量本身。简单来说，它是一个组合运算符，是/=的简写形式。
  
  
• C++：如何调整Windows窗口坐标精度
  C++是一种面向对象编程语言，使用广泛，特别是在Windows平台上。对于Windows窗口应用程序，控制窗口坐标非常重要，因为它们显示在屏幕上的位置可能影响用户界面的外观和操作。
  
  
• "C++多核高级编程：详解PDF书籍"
  C++多核高级编程是一本非常有价值的书籍，该书详细解释了如何在多核环境下进行高级编程。
  
  
• "C++函数的参数为匿名函数"
  在C++中，函数参数可以是匿名函数。匿名函数也被称为lambda函数，是一种能够在程序内部被声明、定义、使用的函数。Lambda函数的语法形式为：[捕获列表](参数列表)
  
  
• C++函数的返回值类型有哪些？
  C++函数的返回值类型是指函数执行完毕后的返回值的数据类型。
  
  
• 如何删除电脑中的所有C++文件？
  在使用电脑过程中，我们可能会有一些不必要或者早已不用的C++文件，这时我们就需要将其删除。但是如何删除电脑中的所有C++文件呢？下面是一些简单有效的方法。
  
  
• C++中如何表示素数？
  在C++中，我们可以使用质数判定算法来表示素数。质数是指除了1和自身外，没有其他因数的正整数。下面介绍两种常用的判断素数的方法。
  
  
• C++四个数从大到小排序
  在C++编程中，对数值进行排序是一项非常基础的操作。当需要对四个数进行排序时，可以使用如下的步骤：
  
  
• 教你如何在DEV c++中运行代码
  如果你正在学习C++编程语言，那么你一定需要一个能够运行你的代码的平台。DEV
  
  
• C++NEW创建二维数组
  C++是一种编程语言，它支持使用类型为double、int、char等的数组。其中，二维数组是一种常见的数据结构，它常用于存储矩阵、表格等数据。
  
  
• 如何在C++中实现以逗号分隔的输入格式？
  在C++中，我们经常需要从命令行接收用户的输入。而有时候，用户需要输入一组数字，这些数字之间用逗号分隔开。那么如何在C++中实现这种输入格式呢？下面是一种简单实用的方法：
  
  
• 如何使用C++将文件传输到服务器？
  在现代网络应用程序设计中，文件传输是必不可少的操作之一。C++是一种高级编程语言，也可以用于构建网络应用程序。在此文章中，我们将介绍如何使用C++将文件传输到服务器。
  
  
• "用C++编写五子棋小游戏代码"
  五子棋是一种非常受欢迎的棋类游戏，玩家需要把五颗棋子连成一条线才能获得胜利。在这个游戏中，每个玩家依次落子，落子的位置需要满足某些规则，然后判断胜负。本文将介绍用C++编写五子棋小游戏代码的过程。
  
  
• 寻找计算机二级C++考试题库的有效途径
  计算机二级C++考试是计算机行业非常重要的一项认证考试，对于想要从事计算机编程开发的人员而言，通过该考试可以增强自己在行业中的竞争力。然而，在备考过程中，其中最困难的一个方面就是找到有效的题库，因为仅凭自己的经验和知识点来备考，很难保证能够
  
  
• C++初学者需要看什么书？
  C++是一种高级编程语言，非常流行，广泛用于游戏开发、机器人技术、操作系统等方面。C++初学者往往会问，“我该看什么书？”在这篇文章中，我们将分享一些适合初学者的C++书籍，并解释为什么这些书适合初学者。
  
  
• C++中的const和override关键字
  C++是一门强大、灵活、高效的编程语言，其语言特性包括const和override关键字。这两个关键字在C++编程中起到非常重要的作用，特别是对于代码的可读性、可维护性以及安全性等方面具有重要的意义。
  
  
• C++重新分配（Redistribution）
  C++重新分配（Redistribution）是在编程中常常使用的一种技术。当我们需要动态分配内存，但是预先并不知道需要分配多少内存时，这种技术可以帮助我们在需要时重新分配内存并加以利用。
  
  
• 2048小游戏C++代码
  2048
  
  
• C++如何合并数组arr1和数组arr2？
  在C++中，合并两个数组arr1和arr2是一件非常基本的操作。这个操作可以通过使用循环遍历两个数组，并将它们中的元素逐一添加到新的数组中来实现。下面是一个简单的代码段，使用这种方法合并两个数组：
  
  
• C和C++，该学哪个？
  编程是当今数字时代不可或缺的技能之一，而C和C++这两门编程语言一直都备受程序员的喜爱。但是对于初学者来说，该从哪门语言开始学习呢？本文将帮助你了解这两门语言的异同，以及适合不同场景下的使用。
  
  
• C++的析构函数
  在C++中，析构函数是一个在对象被销毁时自动调用的特殊函数。它的主要任务是清理对象所占用的资源以及执行必要的收尾工作，使得对象在被销毁时能够安全、合理地释放内存和资源，避免出现内存泄漏、资源浪费等问题。C++中的析构函数与构造函数非常类似，
  
  
• 如何在C++中创建一个新的项目
  对于初学者来说，在C++中创建一个新项目可能会有些困难，但是只要您遵循正确的步骤，就可以创建一个成功的项目。以下是在C++中创建新项目的步骤：
  
  
• C++中字符数组的初始化方法
  C++是一种广泛使用的编程语言，其特性之一就是提供对字符数组的支持。字符数组是一串字符构成的数组，可以用于存储字符串等文本信息。在C++中，有多种方法可以初始化字符数组。
  
  
• C++如何遍历字符串
  C++是一种常用的编程语言，在字符串相关的编程中常常会用到。在处理字符串时，需要对字符串进行遍历，以便对字符串进行各种操作。下面介绍C++如何遍历字符串。
  
  
• C++在工程领域有广泛的应用范围吗？
  C++作为一门面向对象的编程语言，具有极高的灵活性和可扩展性，使其在工程领域中有着广泛的应用。下面将介绍C++在工程领域中的几种应用范围。
  
  
• C++代码出现错误
  C++是一种面向对象的编程语言，在编写代码时难免会出现错误。这些错误可能是语法错误、逻辑错误、运行时错误等等。在编程过程中，通过调试工具和技巧，我们可以找到并修复这些错误。
  
  
• C++如何进行字符串赋值操作？
  在C++程序中，字符串是很常见的数据类型。字符串类型变量可以通过赋值来存储和操作字符串数据，而C++也提供了多种字符串赋值方法。
  
  
• C++的简要介绍
  C++是一种面向对象的编程语言，它在C语言的基础上进行了扩展。C++能够支持多种编程范式，包括面向对象编程、泛型编程和过程式编程。由于其强大的功能和广泛的应用场景，C++是世界上最流行的编程语言之一。
  
  
• C++中的\0代表空字符
  在C++编程中，\0是一个非常重要的字符。这个字符表示的是空字符，也就是空值。C++中，所有的字符都是由ASCII码表来表示的，而\0在ASCII码中的值是0。因此，当我们在C++程序中遇到\0字符时，就可以知道这个字符是一个空字符。
  
  
• C++中实现阶乘的函数
  阶乘是数学中的一种运算，表示正整数n乘以比它小的正整数的乘积，如n!=n×(n-1)×(n-2)×……×2×1。在C++中，可以使用函数来实现阶乘的计算，让代码更简洁、易于维护。
  
  
• C++向量（vector）的扩容原理解析
  C++向量（vector）是一种非常方便的数据结构，它可以根据需要动态增长，减少了人工申请和释放内存的麻烦。那么，C++向量如何实现动态增长呢？这就需要谈到向量的扩容原理了。
  
  
• C++应该使用哪个版本？
  C++是一种高级编程语言，用于开发各种类型的应用程序。随着时间的推移，C++的各种版本也不断更新，因此要选择C++的哪个版本，是一个相对复杂的问题。本文将探讨这个问题，帮助读者更好地了解C++版本。
  
  
• C++代码自动生成工具
  C++代码自动生成工具是一种能够帮助开发人员快速生成C++代码的工具。随着软件开发的不断进步和发展，代码规模和复杂度不断提高，工程师们需要更快、更高效、更精确、更可靠的方式来生成代码，而自动生成工具正是满足这一需求的工具之一。
  
  
• C++中的std::make_shared函数
  C++是一种通用的编程语言，被广泛应用于工业控制、计算机操作系统、客户端应用、数学和科学建模等众多领域。C++的STL(Standard
  
  
• C++代码：判定三个数是否能构成三角形
  在计算机编程中，判断三个数字能否构成一个三角形是一个非常常见的问题。C++是一种流行的编程语言，有许多方法可以帮助我们解决这个问题。
  
  
• C++实现高精度乘法算法
  高精度乘法算法是数字计算中的一个重要问题，在计算机算法中有广泛的应用。C++作为一门流行的编程语言，可以很好地实现高精度算法。本篇文章将介绍如何在C++中实现高精度乘法算法。
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政