素数是指只能被1和它本身整除的正整数，如2、3、5、7、11等。在计算机科学中，素数被广泛应用于密码学、哈希表、质因数分解等领域。在搜索一定范围内的素数时，可以使用素数筛法，它可以在O(n)的时间复杂度内找到所有小于等于n的素数。下面我们来介绍一下如何使用C++实现素数筛法。

首先，我们定义一个数组prime[]，用于标记素数，初值全部为1，即全部视为素数。然后，将2到n间的所有素数找出来，将其倍数标记为0，以此筛掉所有合数。最后，所有标记为1的下标即为素数。

下面是C++代码实现：

#include<iostream>
using namespace std;
const int MAXN = 1000000;
int prime[MAXN + 5]; //筛法中的标记数组
int main()
{
  int n;
  cin >> n;
  //初始化数组
  for (int i = 2; i <= n; i++) 
    prime[i] = 1;
  
  //筛掉所有合数
  for (int i = 2; i <= n; i++)
  {
    if (prime[i])
    {
      for (int j = 2 * i; j <= n; j += i)
        prime[j] = 0;
    }
  }
  
  //输出所有素数
  for (int i = 2; i <= n; i++)
  {
    if (prime[i])
      cout << i << " ";
  }
  
  return 0;
}

以上代码中，首先定义了一个数组prime[]，并将其全部初始化为1表示素数。接着，从2开始遍历数组，如果当前下标i指向的数字为素数，则从其2倍开始，依次将其倍数标记为0，即表示合数。最后遍历prime[]数组，输出其下标为素数的值即可。

使用素数筛法，可以方便地找到小于等于n的素数，且时间复杂度较低。在实际应用中，可以使用该算法进行密码学中的公钥加密、哈希函数中的质数选取、质因数分解等计算。

相似文章
• C++ Primer 和 C++ Primer Plus 有何不同？
  C++
  
  
• C++数学模型：全面了解编程在数学中的应用
  在当今社会中，数学是一门非常重要的学科，无论在哪个领域都有着广泛的应用。而编程作为一种计算机语言，能够将数学模型转化为计算机程序，进行高效的计算和处理。其中，C++是一种常被应用在数学领域的语言。
  
  
• C++语言编程实现四则运算
  C++语言是一种高效、快速的编程语言，是计算机科学中最流行的语言之一。使用C++编程可以轻松实现各种计算操作，比如四则运算。以下将介绍如何用C++编程来实现四则运算。
  
  
• 使用C++构建交互式界面
  在现代计算机科学中，交互式界面（GUI）已经成为用户与计算机之间的常规交互方式。使用GUI界面可以使软件更容易使用，更美观，更易于理解。C++是一种流行的编程语言，开发人员可以使用它来构建GUI界面。本文将介绍如何使用C++构建交互式界面。
  
  
• C++如何实现整行读取文件
  C++是一种广泛使用的编程语言，由于其高效性和灵活性，被广泛应用于各种领域。在C++中，读取文件是一个常见的操作。但是，读取文件时需要注意的一个问题是如何实现整行读取。本文将介绍C++中如何实现整行读取文件的方法。
  
  
• C++中的scanf函数是什么意思？
  在C++中，scanf函数是一种输入函数，它允许用户输入一定的数据并将其存储到定义的变量中。scanf函数使用格式字符串和变量地址来指定输入值以及输出到变量的方式。它具有很多灵活的格式选项，使其能够处理各种不同的输入类型。
  
  
• Java和C++有哪些区别？——来自知乎
  Java和C++是两种常见的编程语言，它们有许多相同的功能，但是也有很多不同之处。下文将从几个方面介绍它们的区别。
  
  
• 《C++中rand函数的头文件》
  C++中rand函数是常用的随机数生成函数之一，它可以根据预设的随机数种子在一定范围内生成指定数量的随机数。那么，rand函数所属的头文件是什么呢？
  
  
• C++如何输出带小数的数据
  在C++中，输出带小数的数据可以通过使用浮点数变量和控制输出格式来实现。下面介绍几种方法：
  
  
• C++中的LPCVOID数据类型详解
  LPCVOID是C++中的一个重要数据类型，在编程中经常被使用到。它代表的是指向一个常量的空指针，是英文
  
  
• C++判断一个数能否被3、5、7整除
  在C++编程中，判断一个数能否被3、5、7整除是一个基本的算法问题。本文将介绍如何使用C++实现这一算法。
  
  
• C++数据排序方法
  C++是一种流行的编程语言，广泛用于开发各种应用程序。数据排序是在程序开发中非常重要的一部分，而C++提供了多种数据排序方法，以便开发人员可以选择最适合他们需求的方法。
  
  
• C++如何输入华氏温度
  C++是一种基于对象的编程语言，广泛应用于计算机科学、数学、物理学和工程学等领域。在C++中，如何输入华氏温度呢？下面我们来介绍一下。
  
  
• C++编辑器应用程序
  C++编辑器应用程序是针对编写C++程序所需的编辑工具。它可以帮助程序员更轻松、高效地编写和调试代码。
  
  
• 「求教」为什么dev c++不能运行.c文件？
  近日，很多dev
  
  
• C++中如何表示素数
  素数是指只能被1和自身整除的数，他们在数学中具有重要的应用。在C++中表示素数有不同的方法，下面我们将介绍一些常用的方法。
  
  
• 更新Microsoft Visual C++ 2010的方法是什么？
  Microsoft
  
  
• C++按从小到大输出三个整数的指针
  在进行C++编程时，经常需要对数字进行排序，然后输出这些数字。在某些情况下，我们需要使用指针来完成这个任务。本文介绍如何使用指针来按从小到大输出三个整数。
  
  
• C++合法的常量：整数常量、浮点数常量、字符常量、字符串常量、布尔常量、指针常量、nullptr常量等。
  在C++编程语言中，常量是指固定值，无法更改的数据类型。C++中，常量被分为几类，包括整数常量、浮点数常量、字符常量、字符串常量、布尔常量、指针常量和nullptr常量。
  
  
• 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++求最大公约数
  最大公约数（Greatest
  
  
• C++编程模型介绍
  C++编程模型是指C++程序的组织结构和执行方式。C++编程模型分为两种：过程式编程模型和面向对象编程模型。
  
  
• C++的发展历程及趋势概述
  C++是一种广泛使用的面向对象编程语言，旨在扩展C语言。它的发展历程始于20世纪80年代，由丹尼斯·里奇的C语言演变而来。C++的主要特点是面向对象、泛型编程和低级别编程，具有高度的可移植性、灵活性和效率。
  
  
• C++简单程序设计原理与实践
  C++是广泛使用的编程语言之一，它具有跨平台、高效、灵活等优点，被广泛应用于游戏开发、嵌入式系统、金融计算等领域。本文将介绍C++的简单程序设计原理和实践。
  
  
• C++ OpenCV读取中文路径下的图像
  许多人在处理图像时喜欢使用OpenCV这个强大的库。但是在读取中文路径下的图像时，就会遇到各种问题，比如显示出来的图片不是想要的结果或者压根读不进来。下面就来介绍一下C++
  
  
• 如何将C++字符串转换为小写驼峰命名格式？
  C++中字符串转小写驼峰命名格式的方法
  
  
• C++中的printf头文件
  在C++编程语言中，printf头文件是一个非常重要的库，它包含了格式化输出函数，使得在输出信息时能够更加方便地进行格式化操作。
  
  
• C++实现九宫格游戏
  九宫格游戏是一种简单而又有趣的游戏，可以帮助我们锻炼思维和逻辑能力。使用C++语言可以轻松实现这个游戏，在此我们分享一下实现的步骤。
  
  
• 学C++要多久的数学基础？
  学习C++是一个扎实的过程，需要掌握一定的数学基础。究竟需要多久的数学基础才能开始学习C++呢？
  
  
• C++程序：求三个数的最大值
  在程序设计中，常常需要求出多个数字中的最大值。在这篇文章中，我们将介绍一个简单的C++程序，用于求解三个数的最大值。
  
  
• C++ 函数头文件
  在使用
  
  
• C++实现顺序查找和二分查找算法
  在计算机科学中，查找算法是指在一组数据中寻找指定的数据元素。常用的两种查找算法是顺序查找和二分查找。在C++中，我们可以使用数组来实现这两种查找算法。
  
  
• VS C++图形界面编程入门指南
  Visual
  
  
• 如何解决Dev C++的编译错误提示问题
  Dev
  
  
• "C++服务器开发精髓：实现高效稳定的网络应用程序"
  C++服务器开发精髓：实现高效稳定的网络应用程序
  
  
• C++语言如何输入字符串？
  C++是一种流行的编程语言，广泛用于操纵算法和计算机科学。在C++中，对于字符串的处理是非常重要的，接下来将会介绍C++语言如何输入字符串。
  
  
• C++对于新手来说适合吗？
  C++是一种广泛使用的计算机编程语言，特别是在操作系统、游戏开发、桌面应用程序和嵌入式系统等领域。对于初学者来说，C++可能会有一定的难度，但是它在编程界占有非常重要的地位，也被许多大公司所采用，因此如果你想学习编程，C++也是一个不错的选
  
  
• 如何用C++最快地将字符写入文件
  在C++中，将字符写入文件是一项经常需要执行的任务。然而，有时候需要在最短的时间内将字符写入文件，这就需要一些技巧和优化，以确保尽可能快地完成任务。下面是一些可以提高C++代码写入文件速度的方法。
  
  
• 如何在C++中判断窗口是否置顶？
  在编写C++程序时，有时需要获取当前窗口是否置顶的状态。这种情况通常出现在窗口置顶的功能中，例如在视频播放软件中，用户可以选择将视频窗口置顶，以保证其一直显示在屏幕最前端。那么如何在C++中判断窗口是否置顶呢？
  
  
• C++中的问号表达式
  C++中的问号表达式是一个三元操作符，用于在两个可能的结果之间进行选择。其基本形式为”
  
  
• 解析激光雷达pcap文件的C++实现
  激光雷达是一种常用的传感器，能够获取周围环境的三维信息。激光雷达处理后的数据一般以
  
  

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