来求出小于等于n的所有的素数。
num = 0;
for(i=2; i<=n; i++)
{ for(j=2; j<=sqrt(i); j++)
if( j%i==0 ) break;
if( j>sqrt(i) ) prime[num++] = i; //这个prime[]是int型,跟下面讲的不同。
}
这就是最一般的求解n以内素数的算法。
素数筛法是这样的:
1.开一个大的bool型数组prime[],大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为false.
2.然后:
for( i=3; i<=sqrt(n); i+=2 )
{ if(prime)
for( j=i+i; j<=n; j+=i ) prime[j]=false;
}
分享到:
相关推荐
这是我个人对原始素数筛选法的一个优化方法,效率提高一倍以上。 (文档内的代码为C/C++代码)
这是我个人对原始素数筛选法的一个优化方法,效率提高一倍以上。
这是我个人对原始素数筛选法的一个优化方法,效率提高一倍以上。
超高速的素数筛选法,大数下10^6区间内筛选所有素数仅需30MS!
在初学c++时经常碰到关于素数的题,但是按传统做法总是会超时,先用筛选法将素数找出。
素数筛选法的改进及C语言实现.pdf
以C++为编程语言,筛选法,编写的求一个数以内的素数
使用筛选法来确定100以内的素数并将其输出 使用时请在dev运行
主要为大家详细介绍了python素数筛选法的相关资料,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
筛选法求素数,在大范围内求素数比其他方法高效很多。
素数筛选法是指一种非常规的素数判定方法,比较高效率; 原理:任何数的整数倍必定不是素数,大于二的偶数必定不是素数。 我们以找出100以内的素数为例,利用原理,我们可以首先排除偶数是素数,然后进一步判断奇数 ...
快速筛选出10亿以内的素数和非素数
用筛选法筛选出1-n之间的素数,效率很高,时间复杂度比平常的算法大大降低,代码拥有详细注释。
用python编写代码找出1000以内的素数和双素数 一、素数 素数(prime number)又称质数,有无限个。除了1和它本身外,不能被其他自然数整除。换句话说就是该数除了1和它本身以外不再有其他的因数的数。 注意:最小的...
用java实现 用筛选法判断一个整数为素数 稍加更改,也可判断一个整数以内的所有素数
内含两个快速统计素数的完整代码,分别是筛选法和大素数模板,统计1亿以内的素数个数并打印所有幸运数字
MIPS汇编下用筛选法求100以内素数,有C语言对照,工具的话,用spim模拟器。
用筛选法筛选出输入的两个数之间的素数比且把他显示在屏幕上。
Matlab课程老师提出的计算素数比赛,在30秒内看谁能用机房里的电脑计算出最多的素数。兴趣使然,自己结合基本的素数定理和筛选法,成功编写这个小程序。目的无他,贴出以供交流和共同进步。