所谓“筛选法”指的是“埃拉托色尼(Eratosthenes)筛法”。他是古希腊的著名数学家。他采取的方法是,在一张纸上写上1到100全部整数,然后逐个判断它们是否是素数,找出一个非素数,就把它挖掉,最后剩下的就是素数。
具体做法如下:
<1> 先将1挖掉(因为1不是素数)。
<2> 用2去除它后面的各个数,把能被2整除的数挖掉,即把2的倍数挖掉。
<3> 用3去除它后面的各数,把3的倍数挖掉。
<4> 分别用4、5…各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。例如找1~50的素数,要一直进行到除数为47为止(事实上,可以简化,如果需要找1~n范围内素数表,只需进行到除数为n^2(根号n),取其整数即可。例如对1~50,只需进行到将50^2作为除数即可。)
如上算法可表示为:
<1> 挖去1;
<2> 用刚才被挖去的数的下一个数p去除p后面各数,把p的倍数挖掉;
<3> 检查p是否小于n^2的整数部分(如果n=1000, 则检查p<31?),如果是,则返回(2)继续执行,否则就结束;
<4> 纸上剩下的数就是素数。
图片示例:
int main() {
int num = 100;
int a[101];
for(int i=0; i<=101; i++) {
a[i] = i;
}
a[1] = 0;
for (int i=2; i<sqrt(num); i++) {
for (int j=i+1; j<=num; j++) {
if (a[j]!=0 && a[j]%i==0) {
a[j] = 0;
}
}
}
for(int i=1, n=0; i<=100; i++) {
if (a[i] != 0) {
printf("%d\t", a[i]);
if(++n%10 == 0) {
printf("\n");
}
}
}
printf("\n");
return 0;
}
转载出处:
http://tieba.baidu.com/p/2442566054#
http://blog.csdn.net/program_think/article/details/7032600
http://blog.chinaunix.net/uid-9078996-id-2010292.html
分享到:
相关推荐
Eratosthenes筛选法求质数.rar
筛选法求素数,在大范围内求素数比其他方法高效很多。
Jupyter 使用列表实现筛选法求素数 使用列表实现筛选法求素数可以极大的提高计算机的运算速率。 maxNumber = int(input("请输入一个大于2的自然数:")) lst = list(range(2,maxNumber)) #最大整数的平方根 m = int...
python语言对于计算机专业的学生,不管是计算机软件还是物联网,都是很重要的一种编程语言,python未来在人工智能方向上是会有很大的贡献程度...python学习—–使用列表实现筛选法求素数目录一、列表实现筛选法求素数的
使用筛选法来确定100以内的素数并将其输出 使用时请在dev运行
【题目描述】 用筛法求出n(2≤n≤1000)以内的全部质数。 【输入】 输入n。 【输出】 多行,由小到大的质数。 【输入样例】 10 【输出样例】 2 3 5 7
Matlab课程老师提出的计算素数比赛,在30秒内看谁能用机房里的电脑计算出最多的素数。兴趣使然,自己结合基本的素数定理和筛选法,成功编写这个小程序。目的无他,贴出以供交流和共同进步。
MIPS汇编下用筛选法求100以内素数,有C语言对照,工具的话,用spim模拟器。
主要介绍了java使用筛选法求n以内的素数示例(java求素数),需要的朋友可以参考下
主要给大家介绍了关于利用C/C++筛选法算素数的相关资料,文中给大家列举了普通枚举法和筛选法两种方法实现的方法示例,文中通过示例代码介绍的非常详细,需要的朋友可以参考借鉴,下面随着小编来一起学习学习吧。
任意输入一数n,求1到n-1的素数。埃式筛选法,效率高!
筛选法求100以内的素数.o
11.埃拉托色尼筛选法求500以内的素数.cpp
用筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时...筛法是最快的求素数方法。
除了自身之外,无法被其它整数整除的数称之为质数,要求质数很简单,但如何快速的求出质数则一直是程式设计人员与数学家努力的课题,在这边介绍一个着名的 Eratosthenes求质数方法。
ACM中,用筛选法求素数,效率很高的算法,希望大家喜欢
源代码 看完写了一个 呵呵 需要的看看
在初学c++时经常碰到关于素数的题,但是按传统做法总是会超时,先用筛选法将素数找出。