筛选法的C++实现

筛选法

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

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

用C++实现筛选法：
以通过筛选法求100以内的素数为例


代码如下:

#include<iostream>
using namespace std;
int main()
{
 int i,j,a[101];//这里定义101大小的数组，是为了和自然数相对应，即：a[2]对应自然数2
 for(i=2;i<100;i++)
     a[i]=1;//完成对数组的初始化操作
 for(i=2;i<100;i++){
  for(j=2*i;j<100;j+=i){
   a[j]=0;//对相应的倍数进行排除
  }
 }
 //执行输出操作
 for(i=2;i<100;i++){
  if(a[i])
  cout<<i<<'\t';
 }
 cout<<endl;
 return 0;
}

一些思考和优化
以前学习计算素数的算法的时候，有一个比较普遍的优化的算法。

也就是用


代码如下:

for(i=1;i<(j/2);i++)

或者


代码如下:

for(i=1;i<sqrt(j);i++)//使用sqrt()函数需要引入math.h这个头文件

来替代


代码如下:

for(i=1;i<j;i++)

可以显著的降低算法的复杂度

一开始直接使用，不知道是什么原理。后来看了看，原来原理是这样的：

以sqrt(j)代替i为例

求素数最基本的方法，是用i去除以2到j-1之间的所有的整数，如果有可以整除的情况，则不是素数；如果都不可以整除，则是素数。

而i=sqrt(j)*sqrt(j)

我们用i去除以2到sqrt(j)之间的所有的整数，这就可以覆盖2到i-1之间的所有的整数。

设2<k<sqrt(j)，则若j%k==0，则sqrt(j)<m=(j%k)<j-1。

也就是说，因为是除法运算求整除的运算，所以除以小的可以整除，可就是除以相应的大的可以整除。

优化之后的代码：


代码如下:

#include<iostream>
#include<math.h>
using namespace std;
int main()
{
 int i,j,a[101];//这里定义101大小的数组，是为了和自然数相对应，即：a[2]对应自然数2
 for(i=2;i<100;i++)
     a[i]=1;//完成对数组的初始化操作
 for(i=2;i<sqrt(100);i++){
  for(j=2*i;j<100;j+=i){
   a[j]=0;//对相应的倍数进行排除
  }
 }
 //执行输出操作
 for(i=2;i<100;i++){
  if(a[i])
  cout<<i<<'\t';
 }
 cout<<endl;
 return 0;
}

赞 (0)

相关推荐

  • java使用筛选法求n以内的素数示例(java求素数)

    复制代码 代码如下: /** * @author jxqlovedn * 埃拉托斯特尼素数筛选法,请参考:http://zh.wikipedia.org/zh-cn/埃拉托斯特尼筛法 */public class AratosternyAlgorithm { public static void getPrimes(int n) {  if(n < 2 || n > 1000000)   // 之所以限制最大值为100万,是因为JVM内存限制,当然有其他灵活方案可以绕过(比如位图法)   th

  • c++素数筛选法

    c++素数筛选法

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

  • 筛选法的C++实现

    筛选法 介绍:筛选法又称筛法,是求不超过自然数N(N>1)的所有质数的一种方法.据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274-194年)发明的,又称埃拉托斯特尼筛子. 具体做法是:先把N个自然数按次序排列起来.1不是质数,也不是合数,要划去.第二个数2是质数留下来,而把2后面所有能被2整除的数都划去.2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去.3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去.这样一直做下去,就会把不超

  • python素数筛选法浅析

    python素数筛选法浅析

    原理: 素数,指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数.在加密应用中起重要的位置,比如广为人知的RSA算法中,就是基于大整数的因式分解难题,寻找两个超大的素数然后相乘作为密钥的.一个比较常见的求素数的办法是埃拉托斯特尼筛法(the Sieve of Eratosthenes) ,说简单一点就是画表格,然后删表格,如图所示: 从2开始依次往后面数,如果当前数字一个素数,那么就将所有其倍数的数从表中删除或者标记,然后最终得到所有的素数. 有一个优化: 标记2和3的倍数

  • python使用筛选法计算小于给定数字的所有素数

    本文实例为大家分享了python计算小于给定数字的所有素数的具体代码,供大家参考,具体内容如下 代码思路:首先列出指定范围内所有候选数字,然后从前往后依次选择一个数字去除以后面所有数字,能够被整除的肯定不是素数,把这些数字过滤掉,然后重复这个过程,直到选择的除数大于最大数字的平方根为止.代码主要演示内置函数filter()和切片的用法,实际上这个算法的效率并不是很高. def primes2(maxNumber): '''筛选法获取小于maxNumber的所有素数''' #待判断整数 lst =

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

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

  • python如何在列表、字典中筛选数据

    python如何在列表.字典中筛选数据? 实际问题有哪些? 1.过滤掉列表[3,9,-1,10.-2......] 中负数 2.筛选出字典 {'li_ming':90,'xiao_hong':60,'li_kang':95,'bei_men':98} 中值高于90的项 3.筛选出集合{3,9,-1,10.-2......]中能被3整除的数 问题1如何解决? 最普通方法: #!/usr/bin/python3 def filter_l(data): res = [] for i in data:

  • Python cookbook(数据结构与算法)筛选及提取序列中元素的方法

    本文实例讲述了Python筛选及提取序列中元素的方法.分享给大家供大家参考,具体如下: 问题:提取出序列中的值或者根据某些标准对序列做删减 解决方案:列表推导式.生成器表达式.使用内建的filter()函数 1.列表推导式方法:存在一个潜在的缺点,如果输入数据非常大可能会产生一个庞大的结果,考虑到该问题,建议选择生成器表达式 # Examples of different ways to filter data mylist = [1, 4, -5, 10, -7, 2, 3, -1] prin

  • GO语言求100以内的素数

    本文实例讲述了GO语言筛选法求100以内的素数.分享给大家供大家参考.具体实现方法如下: 思路:找出一个非素数就把它挖掉,最后剩下就是素数. 下面就来欣赏一下go简洁的代码吧 目前不支持GO的代码插入,使用xml的代替一下. 复制代码 代码如下: package main import (     "fmt"     "math" ) func main() {     var i, j, n int     var a [101]int     for i = 1

  • 堆排序算法的讲解及Java版实现

    堆是数据结构中的一种重要结构,了解了"堆"的概念和操作,可以快速掌握堆排序. 堆的概念 堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+2. 堆

随机推荐