[经典算法] Eratosthenes筛选求质数

时间:2023-01-14 15:29:01

题目说明:

除了自身之外,无法被其它整数整除的数称之为质数,要求质数很简单,但如何快速的求出质数则一直是程式设计人员与数学家努力的课题,在这边介绍一个著名的 Eratosthenes求质数方法。

题目解析:

首先知道这个问题可以使用回圈来求解,将一个指定的数除以所有小于它的数,若可以整除就不是质数,然而如何减少回圈的检查次数?如何求出小于N的所有质数?
首先假设要检查的数是N好了,则事实上只要检查至N的开根号就可以了,道理很简单,假设A*B = N,如果A大于N的开根号,则事实上在小于A之前的检查就可以先检查到B这个数可以整除N。不过在程式中使用开根号会精确度的问题,所以可以使用 i*i <= N进行检查,且执行更快。
再来假设有一个筛子存放1~N,例如:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ........ N

先将2的倍数筛去:

2 3 5 7 9 11 13 15 17 19 21 ........ N

再将3的倍数筛去:

2 3 5 7 11 13 17 19 ........ N

再来将5的倍数筛去,再来将7的质数筛去,再来将11的倍数筛去........,如此进行到最后留下的数就都是质数,这就是Eratosthenes筛选方法(Eratosthenes Sieve Method)。
检查的次数还可以再减少,事实上,只要检查6n+1与6n+5就可以了,也就是直接跳过2与3的倍数,使得程式中的if的检查动作可以减少。

程序代码:

#include <iostream>
#include <vector>
#include <algorithm>
#include <gtest/gtest.h>
using namespace std; vector<int> EratosthenesPrime(int nSize)
{
bool* Primes = new bool[nSize];
memset(Primes, true, sizeof(bool)* nSize); for (int i=2; i * i <= nSize; ++i)
{
if (Primes[i])
{
for (int j = i*i; j < nSize; j+=i)
{
Primes[j] = false;
}
}
} vector<int> Result;
for (int i=2; i < nSize; ++i)
{
if (Primes[i])
{
Result.push_back(i);
}
} delete[] Primes; return Result;
} TEST(Algo, tEratosthenesPrime)
{
vector<int> Result = EratosthenesPrime(100);
cout << "N:100 " << Result.size() << endl;
for (vector<int>::size_type i=0; i<Result.size(); ++i)
{
if (i % 16 == 0)
cout << endl; cout << Result[i] << " ";
}
cout << endl << endl; Result = EratosthenesPrime(500);
cout << "N:500 " << Result.size() << endl;
for (vector<int>::size_type i=0; i<Result.size(); ++i)
{
if (i % 16 == 0)
cout << endl; cout << Result[i] << " ";
}
cout << endl << endl; Result = EratosthenesPrime(1000);
cout << "N:1000 " << Result.size() << endl;
for (vector<int>::size_type i=0; i<Result.size(); ++i)
{
if (i % 16 == 0)
cout << endl; cout << Result[i] << " ";
}
cout << endl << endl;
}

参考引用:

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[经典算法] Eratosthenes筛选求质数的更多相关文章

  1. C语言程序设计100例之(12):Eratosthenes筛法求质数

    例12   Eratosthenes筛法求质数 问题描述 Eratosthenes筛法的基本思想是:把某范围内的自然数从小到大依次排列好.宣布1不是质数,把它去掉:然后从余下的数中取出最小的数,宣布它 ...

  2. &lbrack;经典算法&rsqb; 蒙地卡罗法求 PI

    题目说明: 蒙地卡罗为摩洛哥王国之首都,该国位于法国与义大利国境,以赌博闻名.蒙地卡罗的基本原理为以乱数配合面积公式来进行解题,这种以机率来解题的方式带有赌博的意味,虽然在精确度上有所疑虑,但其解题的 ...

  3. python经典算法题:求字符串中最长的回文子串

    题目 给定一个字符串 s,找到 s 中最长的回文子串.你可以假设 s 的最大长度为 1000. 示例 1: 输入: "babad" 输出: "bab" 注意: ...

  4. c经典算法

    1. 河内之塔 说明 河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内为越战时 北越的首都,即现在的胡志明市:1883年法国数学家 Ed ...

  5. Java经典算法大全

    1.河内之塔.. 2.Algorithm Gossip: 费式数列. 3. 巴斯卡三角形 4.Algorithm Gossip: 三色棋 5.Algorithm Gossip: 老鼠走迷官(一) 6. ...

  6. Eratosthenes筛选法求解质数

    问题说明: 除了自身之外,无法被其它整数整除的数称之为质数,要求质数很简单,但如何快速的求出质数则一直是程式设计人员与数学家努力的课题, 在这边介绍一个着名的 Eratosthenes求质数方法. 解 ...

  7. &lbrack;算法&rsqb;浅谈求n范围以内的质数(素数)

    汗颜,数学符号表达今天才学会呀-_-# 下面是百度百科对质数的定义 质数(prime number)又称素数,有无限个. 质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数. 求质数的方法 ...

  8. Eratosthenes筛选法计算质数

    <C和指针>第6章第4道编程题: 质数就是只能被1和本身整除的数.Eratosthenes筛选法是一种计算质数的有效方法.这个算法的第一步就是写下所有从2至某个上限之间的所有整数.在算法的 ...

  9. 求质数算法的N种境界&lbrack;1&rsqb; - 试除法和初级筛法

    ★引子 前天,俺在<俺的招聘经验[4]:通过笔试答题能看出啥?>一文,以"求质数"作为例子,介绍了一些考察应聘者的经验.由于本文没有*内容,顺便就转贴到俺在CSD ...

随机推荐

  1. jQuery动画

    一.显示和隐藏 hide().show() 1.show():显示被选的元素 2.hide():隐藏被选的元素 3.toggle():对被选元素进行隐藏和显示的切换 语法: $(selector).h ...

  2. javaWeb之maven多数据库环境的配置信息

    在使用maven构建的web项目里,不管采用的是什么orm框架,数据库写死了必然不是最灵活的方式.所以通过maven 的buid方式可以动态的分配数据库信息 比如在jdbc.properties中,可 ...

  3. LNMP平台搭建---Nginx安装篇

    在上一篇博文<LNMP平台搭建---Linux系统安装篇>中,我们安装了CentOS版本的Linux操作系统,现在,我们来安装一个Web服务器,大标题写着LNMP,其中的N就是Nginx, ...

  4. I2C控制器的Verilog建模之二

    前言:接着上一篇的I2C写操作,今天要实现一个I2C的读操作.虽然在ADV7181B配置内部寄存器时没有必要使用到读操作,但是为了进一步确认寄存器是否在I2C写模块下被正确配置,这一步是必不可少的. ...

  5. React Native在Windows下修改js代码后reload无效

    iOS下因为有watchman这个插件,所以启动很快(npm start),而Windows下则非常慢,最要命的是遇到了修改js文件后,点击reload居然一直是请求的缓存bundle,泪崩... 后 ...

  6. HTML——使用表格对表单进行布局

    watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc3Vuc2h1bWlu/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA ...

  7. CentOS7开机提示welcome to emergency mode!after logging in&period;&period;&period;

    CentOS7.3昨天用的还好好的的,但是今天开机提示如下(如图提示): welcome to emergency mode!after logging in ,type "journalc ...

  8. URI 方法 encodeURI&lpar;&rpar; encodeURIComponent&lpar;&rpar; docodeURI&lpar;&rpar; decodeURIComponent&lpar;&rpar;

    URI 方法  encodeURI()  encodeURIComponent()  docodeURI()  decodeURIComponent()   var sUri = “http://ww ...

  9. 微信小程序 人脸识别登陆模块

    微信小程序---人脸识别登陆的实现 关键词:微信小程序 人脸识别 百度云接口 前言 这是一篇关于一个原创微信小程序开发过程的原创文章.涉及到的核心技术是微信小程序开发方法和百度云人脸识别接口.小程序的 ...

  10. Non-decreasing Array

    Given an array with n integers, your task is to check if it could become non-decreasing by modifying ...