【方法一】
【代码一】
-
-
intIsPrime(inta){
-
-
if(a<=1){
-
return0;
-
}
-
-
intbound=(int)sqrt(a)+1;
-
for(inti=2;i<bound;i++){
-
-
if(a%i==0){
-
return0;
-
}
-
}
-
return1;
-
}
【方法二】
【代码二】
-
#defineMAXSIZE10001
-
-
intMark[MAXSIZE];
-
intprime[MAXSIZE];
-
-
-
intPrime(){
-
intindex=0;
-
memset(Mark,0,sizeof(Mark));
-
for(inti=0;i<MAXSIZE;i++){
-
-
if(Mark[i]==1){
-
continue;
-
}
-
else{
-
-
prime[index++]=i;
-
-
for(intj=i*i;j<MAXSIZE;j+=i){
-
Mark[j]=1;
-
}
-
}
-
}
-
returnindex;
-
}
【方法三】
这种方法比较好理解,初始时,假设全部都是素数,当找到一个素数时,显然这个素数乘上另外一个数之后都是合数
把这些合数都筛掉,即算法名字的由来。但仔细分析能发现,这种方法会造成重复筛除合数,影响效率。
比如10,在i=2的时候,k=2*15筛了一次;在i=5,k=5*6 的时候又筛了一次。所以,也就有了快速线性筛法。
【代码三】
-
intMark[MAXSIZE];
-
intprime[MAXSIZE];
-
-
-
intPrime(){
-
intindex=0;
-
memset(Mark,0,sizeof(Mark));
-
for(inti=2;i<MAXSIZE;i++)
-
{
-
-
if(Mark[i]==0){
-
prime[index++]=i;
-
}
-
-
for(intj=0;j<index&&prime[j]*i<MAXSIZE;j++)
-
{
-
Mark[i*prime[j]]=1;
-
if(i%prime[j]==0){
-
break;
-
}
-
}
-
}
-
returnindex;
-
}
利用了每个合数必有一个最小素因子。每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。代码中体现在:if(i%prime[j]==0)break;prime数组 中的素数是递增的,当 i 能整除 prime[j],那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。在满足i%prme[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。
参考博文:点击打开链接
习题练习:点击打开链接
分享到:
相关推荐
一种快速素数筛法
素数筛法求得0-1000000内所有素数,利用空间换时间的方法降低算法时间复杂度,使用一维数组,初始化全为0,当数组下标对应的值为素数时,对应的数组值变为1,最后便利整个数组,将所有值为1的数组下标保存在第一数组...
革命性素数算法:计算1亿内素数只要1.6秒 算法基本跟之前发的C#版相同(http://download.csdn.net/source/690005内有算法描述),由我的朋友杨力2年前设计,时间复杂O(n)。我对其进行了革命性的数据结构改进,空间...
前言在数论领域,解决问题时经常会有得到素数的需求如何快速得到一定范围内的所有素数,就成了人们一直追求的问题这里列举一些素数筛法,也许会有帮助埃氏筛法(Sieve
由于算法相对复杂,素数筛法的运行时间会更高 在大数区间 [108,109] 内随机选取的平均运算时间是 素数筛: 开方法 ≈ 2: 1 部分运行结果可见下图,前4个数为比较有代表性的测试数字,最后为4中的平均时间 主要思路 ...
求素数问题。埃拉托色尼筛法(Sieve of Eratosthenes)是一种用来求所有小于N的素数的方法。从建立一个整数2~N的表着手,寻找i˂的整数,编程实现此算法,并讨论运算时间。
讲述O(n)筛法求素数的经典论文 ---------- A Linear Sieve Algorithm for Finding Prime Numbers David Gries Cornell University Jayadev Misra University of Texas at Austin
基于MPI实现埃拉托斯特尼筛法及性能优化实验报告.docx
编程实现加解密的基本运算。 (1)移位 (2)逻辑运算 (3)欧几里德算法求两个整数的最大公约数 (4)素数的判定和寻找(筛法)
蓝桥杯算法辅导 ,算法作为蓝桥杯竞赛的一个核心内容,作为参赛者需要掌握以下常用的...素数筛法 整数的基本性质与应用 浮点数的注意事项 经典的递归问题 递归与循环 代码使用java编写,包含了AVL树的模型图作为参考,
可以批量求出 大范围内的 素数。这个算法有点复杂。想要最好的可以去我的资料中 找另外一个。反正都是免费的~
7.数学算法:包括快速幂、欧几里得算法、 素数筛法等 8.数据结构:包括树、 堆、图等数据结构,需要熟练掌握其基本原理、 结构特点、操作等方面的内容。 9.其他算法: 例如双指针算法、 滑动窗口算法、 分治算法、 ...
埃拉托斯特尼是一位古希腊数学家,他在寻找整数N以内的素数时,采用了一种与众不同的方法:先将2-N的各数写在纸上: 在2的上面画一个圆圈,然后划去2的其他倍数;第一个既未画圈又没有被划去的数是3,将它画圈,再...
埃氏筛法0.8秒搜寻1亿以内素数并统计个数。 埃氏筛法搜寻1亿以内素数,标记、统计并输出个数和耗时。网络类似算法不少,但fortran版本未见,至少是中文网站上尚未见到。本代码部分减少了重复标记,效率更高。
3. Sieve Prime素数筛法 4. Module Inverse模逆元 5. Extended Euclid扩展欧几里德算法 6. Modular Linear Equation模线性方程(同余方程) 7. Chinese Remainder Theorem中国余数定理(互素于非互素) 8. Euler ...
以模6为基本的素数算法,这是一种素数的新筛法,builderC++6.0下测试通过.
埃拉托斯特尼筛法,简称埃氏筛或爱氏筛,是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。
Eratosthenes素数筛法 Sieve-of-Erotosthenes 指针版的单向链表 Singly-Linked-List(Pointer) 跳表 Skip-List ST表 Sparse-Table 伸展树 Splay 博弈论SG函数 Sprague-Grundy 栈的基本操作 Stack 递推法求解无...
欧拉筛法,简称欧拉筛或是欧式筛,又因为其O(n)的时间复杂度而被称为线性筛。 欧拉筛将合数分解为(最小质因数 * 一个合数)的形式,通过最小质因数来判断当前合数是否已经被标记过,与埃氏筛相比,不会对已经被...
python零基础初学者 体验程序