简介
埃拉托色尼选筛法(the Sieve of Eratosthenes)简称埃氏筛法,是古希腊数学家埃拉托色尼(Eratosthenes)提出的一种筛选法。 是针对自然数列中的自然数而实施的,它的容斥原理之完备性条件是p=H~。
步骤
(1)先把1删除(因为1不是质数)(2)把2留下(最小的偶数质数),然后把2的倍数删去
(3)把3留下,然后把3的倍数删去
(4)把5留下,然后把5的倍数删去
(5)....继续进行下去,直到把所有数要么留下,要么删除。(所有偶数被删去)
如图:
eratosthenes筛选法的c语言实现(不是最优解,容易看懂)
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define SIZE 1000000
int main()
{
int i; /*i表示整数和对应的下标*/
int j; /*j表示正要处理的质数j之前的已处理j之后的未处理*/
int k; /*k表示正在处理的j的倍数从2开始到j*k<SIZE*/
int a[SIZE]; /*下标表示整数内容判断是否为质数*/
int *p; /*控制循环*/
for(p = a; p < a + SIZE; ++p) /*初始化数组全是TRUE*/
{
*p = TRUE;
}
a[0] = a[1] = FALSE; /*设置前面两个不是质数的数的状态为FALSE*/
i = 2;
for(p = a; p < a + SIZE; ++p)
{
while(i < SIZE) /*找到下一个质数*/
{
if(a[i++] == TRUE)
{
j = i - 1;
break;
}
}
for(k = 2; j * k < SIZE && i < SIZE; ++k) /*处理质数的倍数*/
{
a[j *k] = FALSE;
}
}
for(p = a; p < a + SIZE; ++p) /*打印出质数*/
{
if(*p == TRUE)
{
printf("%8d", p - a);
}
}
printf("/n");
return 0;
}
分享到:
相关推荐
可以批量求出 大范围内的 素数。这个算法有点复杂。想要最好的可以去我的资料中 找另外一个。反正都是免费的~
埃拉托色尼素数筛选法。代码示例。
该程序的灵感来自艺术品: Sieb des Eratosthenes(Eratosthenes 的筛子)(1971 年)来自 Rune Mields(德国画家,1935 年生) 这幅来自她的 9 幅面板艺术作品的作品将素数显示为白点。 左栏显示89栏排列的数字,...
素数也可以用六列的埃拉托色尼筛法来形象化。 筛子是在 Html 中创建的,可以将它保存在一个文件中,以便在程序关闭后也可以用任何其他浏览器打开它。 如果浏览器支持 JavaScript,点击它应该可以显示非质数的...
一种应用“Eratosthenes 筛法”来查找和显示由开始和结束指定的整数之间的素数的算法。 在显示的末尾,添加找到了多少个素数(计数)以及找到它们所需的时间(时间)。 这是一个我刚刚玩过的应用程序,试图在 ...
我的Prime 埃拉托色尼筛使用埃拉托色尼筛法查找所有质数的 Android 应用程序。
11.埃拉托色尼筛选法求500以内的素数.cpp
还记得小学数学老师布置的家庭作业问题,您必须确定某个五位数是否为质数? 您可能用来完成该作业的算法称为试算,而且速度很慢。 在确定小于足够大整数的所有素数时,即使是计算机也需要一段时间才能使用此算法。...
求素数问题。埃拉托色尼筛法(Sieve of Eratosthenes)是一种用来求所有小于N的素数的方法。从建立一个整数2~N的表着手,寻找i˂的整数,编程实现此算法,并讨论运算时间。
java笔试题算法多种语言的埃拉托色尼筛子 以各种语言实现 Eratosthenes 筛以展示 GraalVM 和 Truffle 的强大功能。 请先下载后再进行实验。 已经过测试可以与版本19.3.1 。 Ruby速度 使用以下命令可以发现 GraalVM ...
本文讲的是筛选法的C++实现, 筛选法又称筛法,是求不超过自然数N(N>1)的所有质数的一种方法。据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274~194年)发明的,又称埃拉托斯特尼筛子。
埃拉托色尼筛法(Sieve of Eratosthenes)是一种用来求所有小于N的素数的方法。从建立一个整数2~N的表着手,寻找i˂ 的整数,编程实现此算法,并讨论运算时间。(1) 2. 猴子吃桃子问题。有一群猴子摘了一堆桃子,...
对于给定范围、给定钱币面额,借助埃拉托色尼筛法、迪杰斯特拉算法、图的广度优先遍历算法思想,设计了一个快速计算每个数值的最小钱币数量方法,即最少钱币数量筛法来计算平均纸张数量;对于给定范围、给定数量的...
采用Sieve of Eatosthenes (埃拉托色尼筛选法)方法搜索素数小程序。(c++实现)
埃拉托色尼筛在eratosthenes.scss文件中实现。 运行此代码后,将创建primes列表。 对于素数,相应索引的值(从 1 开始)将为true 。 这个算法不是最优的。 在 SCSS 中,您不能用索引替换列表元素。 为了解决这个问题...
快速筛选素数:埃拉托色尼筛选法 只有一行的算法:欧几里得算法求解最大公约数 求幂乘:反复平法法 筛选素数 小学的知识点,不解释了; bool isPrime(int d){//判断是否是素数 if(d==2) return true; if(d<2|...
埃拉托色尼法筛选素数
埃拉托色尼筛 Android 实习编码挑战 描述 在我的代码中,我使用以下三行来禁用此应用程序的横向模式: getWindow().addFlags(WindowManager.LayoutParams.FLAG_KEEP_SCREEN_ON); setRequestedOrientation...
埃拉托色尼筛法(Sieve of Eratosthenes)是一种用来求所有小于N的素数的方法。从建立一个整数2~N的表着手,寻找i˂ 的整数,编程实现此算法,并讨论运算时间
埃拉托色尼这是一个允许用户输入数字的应用程序,然后它会输出每个素数,直到输入的数字为止。安装说明: Clone repository and open the index.html file.错误报告: None known作者: 亚历克斯·考夫曼和卢克·钦...