C/C++利用筛选法算素数的方法示例

什么是求素数

素数指的是因子只有1和本身的数（1不是素数），求解素数在数学上应用非常广泛，而求解n以内的素数也是我们编程时常遇到的问题，在这个问题上，筛选法求解素数运行得非常快。

i在2到n-1之间任取一个数,如果n能被整除则不是素数，否则就是素数

称筛法

筛选法又称筛法，是求不超过自然数N（N>1）的所有质数的一种方法。据说是古希腊的埃拉托斯特尼（Eratosthenes，约公元前274～194年）发明的，又称埃拉托斯特尼筛子。

具体做法是：

先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。）

普通枚举法:

#include <iostream>
#include <string>
#include <cmath>
#include <cstring>
using namespace std;
bool isPlain(int x){
 if(x<2) return false;
 else{
 for(int i=2;i<x;i++)
 {
 if(!(x%i))
 return false;
 }
 }
 return true;
}
int main()
{
 int n;
 cin>>n;
 int cot=0;
 for(int j=0;j<n;j++){
 if(isPlain(j)){
 cout<<j<<((++cot%7==0)?"\n":"\t");
 }
 }
}

筛选法:

原始版本:

#include <iostream>
#include <string>
#include <cmath>
#include <cstring>
using namespace std;
int main()
{
 int n;
 cin>>n;
 bool* ans=new bool[n];
 memset(ans,true,sizeof(bool)*n);//
 ans[0]=false;
 ans[1]=false;
 for(int i=2;i<n;i++){
 if(ans[i]){
 for(int j=i*2;j<n;j+=i){//倍数取整
 ans[j]=false;
 }
 }
 }
 int col = 0;
 for(int i=0;i<n;i++){
 if(ans[i]){
 cout<<i<<" ";
 }
 }
 return 0;
}

改进版本

#include <iostream>
#include <string>
#include <cmath>
#include <cstring>
#include <bitset>
using namespace std;
int main()
{
 int n;
 cin>>n;
 bitset<100000> ans;
 ans.set(0);
 ans.set(1);
 for(int j=2; j<=sqrt(n); j++)
 {
 for(int i=2*j; i < n; i+=j)
 {
 ans.set(i);
 }
 }
 int cot=0;
 for(int i=0; i<n; i++)
 {
 if(ans[i]!=1)
 {
 cout<<i<<((++cot%7==0)?"\n":"\t");
 }
 }
}

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对我们的支持。

赞 (0)

相关推荐

  • C++回文数及素数问题计算方法

    C++回文数及素数问题计算方法

    本文实例讲述了C++回文数及素数问题计算方法.分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 16 日 * 版 本 号:v1.0 * * 输入描述: 编制一个返回值为bool型的函数isPrimer(),用于判断参数是否为素数,isPalindrome()用于判断参数是否是回文数,调用函数回答以下问题(可以分别编制几个程序完成,也可以在一个main()函数中完成,输出时,用明显的提示语,说明正在完成哪个任务.) (1)输出10000以内的所有素

  • C++如何判断一个数字是否为质数

    关于素数的算法是程序竞赛比较重要的数论知识,我们来看通常会使用的几个算法. 我们先来复习几个基本概念: 质数:对于大于1的自然数,若除了1和它本身,没有别的因数,则称这个数为质数,质数也叫素数.反之,称其为合数. #include<iostream> #include<cmath> using namespace std; void IsPrime(int); int main() { int Input; cout << "请输入要判断的数字:";

  • C++ 实现求小于n的最大素数的实例

    C++ 实现求小于n的最大素数的实例 枚举就是基于已有知识镜像答案猜测的一种问题求解策略 问题:求小于n的最大素数 分析: 找不到一个数学公式,使得根据N就可以计算出这个素数     我们思考: N-1是素数么?N-2是素数吗?...         所以我们就是判断N-K是否为素数:     N-K是素数的充分必要条件:N-K不能被[2,n-k)中任何一个整除         判断N-K是否为素数的问题可以转化为:     求小于N-K的全部素数(求"小于N的最大素数"中的条件是&q

  • c++素数筛选法

    c++素数筛选法

    素数(又称质数):指在大于一的自然数中,只能被1和它自身整除的自然数: 素数筛选法是指一种非常规的素数判定方法,比较高效率: 原理:任何数的整数倍必定不是素数,大于二的偶数必定不是素数. 我们以找出100以内的素数为例,利用原理,我们可以首先排除偶数是素数,然后进一步判断奇数 实现将偶数标记为0,素数标记为1:(也可以用一个bool数组将偶数标记为false,奇数标记为true) 下面是全部代码 #include <iostream> #include <cmath> #defin

  • C/C++利用筛选法算素数的方法示例

    什么是求素数 素数指的是因子只有1和本身的数(1不是素数),求解素数在数学上应用非常广泛,而求解n以内的素数也是我们编程时常遇到的问题,在这个问题上,筛选法求解素数运行得非常快. i在2到n-1之间任取一个数,如果n能被整除则不是素数,否则就是素数 称筛法 筛选法又称筛法,是求不超过自然数N(N>1)的所有质数的一种方法.据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274-194年)发明的,又称埃拉托斯特尼筛子. 具体做法是: 先把N个自然数按次序排列起来.1不是质数,也不是合

  • 详解利用jsx写vue组件的方法示例

    前言 本文主要给大家介绍的是关于利用jsx写vue组件,下面话不多说,来一起看看详细的介绍吧. 我们平常写vue的组件时,一般都是用的是模版,这种方式看起来比较简洁,而且vue作者也推荐使用这个方式,但是这种方式也有一些它的弊端,例如模版调试麻烦,或者在一些场景下模版描述可能没那么简单和方便. 下面我们要讲的是如何在vue里面写jsx,知道react的人应该都知道jsx,jsx的一个特性就是非常灵活,虽然有的人觉得jsx很丑陋,把逻辑都写到模版的感觉,但萝卜青菜各有所爱,适合自己适合团队的就是最

  • 利用python求相邻数的方法示例

    前言 本文主要给大家介绍了关于利用python求相邻数的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍: 什么是相邻数? 比如5,相邻数为4和6,和5相差1的数,连续相差为1的一组数 需求: 遍历inputList 所有数字,取出所有数字,判断是否有相邻数, 不相邻数字 和 相邻数字 都以 "数组"形式 添加到 outputList 中, 并且 每个"数组" 里 第一位 递减 补全两位数,末位 递增 补全两位数, 每一个数不能小于0, 不能大

  • Python利用Beautiful Soup模块修改内容方法示例

    前言 其实Beautiful Soup 模块除了能够搜索和导航之外,还能够修改 HTML/XML 文档的内容.这就意味着能够添加或删除标签.修改标签名称.改变标签属性值和修改文本内容等等.这篇文章非常详细的给大家介绍了Python利用Beautiful Soup模块修改内容的方法,下面话不多说,来看看详细的介绍吧. 修改标签 使用的示例 HTML 文档还是如下: html_markup=""" <div class="ecopyramid">

  • Node.js利用console输出日志文件的方法示例

    通常我们在写Node.js程序时,都习惯使用console.log打印日志信息,但这也仅限于控制台输出,有时候我们需要将信息输出到日志文件中,实际上利用console也可以达到这个目的的,今天就来简单介绍一下. 我们首先创建如下文件: // index.js let fs = require('fs'); let options = { flags: 'a', // append模式 encoding: 'utf8', // utf8编码 }; let stdout = fs.createWri

  • python利用matplotlib库绘制饼图的方法示例

    python利用matplotlib库绘制饼图的方法示例

    介绍 matplotlib 是python最著名的绘图库,它提供了一整套和matlab相似的命令API,十分适合交互式地进行制图.而且也可以方便地将它作为绘图控件,嵌入GUI应用程序中. 它的文档相当完备,并且 Gallery页面 中有上百幅缩略图,打开之后都有源程序.因此如果你需要绘制某种类型的图,只需要在这个页面中浏览/复制/粘贴一下,基本上都能搞定. matplotlib的安装方法可以点击这里 这篇文章给大家主要介绍了python用matplotlib绘制饼图的方法,话不多说,下面来看代码

  • 利用Golang解析json数据的方法示例

    本文主要给大家介绍的是关于Golang解析json数据的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍: 使用 Golang 解析 json 数据,这种 json 格式是对象的数组,官方文档有一个示例: var jsonBlob = []byte(`[ {"Name": "Platypus", "Order": "Monotremata"}, {"Name": "Quoll

  • iOS中利用KeyChain保存用户信息的方法示例

    iOS中利用KeyChain保存用户信息的方法示例

    前言 说到保存用户名和密码,以前有用过本地的数据库来保存,也接触过用userdefault来保存,后来在一个项目中发现了一个新的方法--用Keychain来保存.下面话不多说了,直接通过示例代码来介绍吧. 方法示例 一.新建一个LYKeychainTool类,导入系统Security框架 ,LYKeychainTool.h文件实现如下: // // LYKeychainTool.h // keyChainTest // // Created by Liyu on 2017/6/2. // Cop

  • Js利用console计算代码运行时间的方法示例

    前言 本文主要给大家介绍了关于Js用console计算代码运行时间的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 需求 如果学习前端一定时间以后,就会考虑性能方面的问题.那么问题来了,我们怎么计算出一段代码的运行时间呢? 使用console.log配合Date对象计算 比如,我们计算sort方法排序十万个随机数组成的数组需要用多长时间的话,可以这么写: var arr = []; for(var i=0; i<100000; i++){ arr.push(Math.

  • js利用prototype调用Array的slice方法示例

    复制代码 代码如下: <script type="text/javascript"> function fn(name){ if(typeof name === "string"){ var args = Array.prototype.slice.call( arguments, 1 ); for(var i=0;i<args.length;i++){ alert(args[i]);//结果: 111 222 } } } function cal

随机推荐