🤡前言🤡
素数是我们中学时代就接触过的概念,今天呢我们又提起了他足以见到了他对我们的重要性😻
我们再来重温一下素数（质数）的概念：
素数：只有两个正因数（1和它本身）的自然数即为质数。比1大但不是素数的数称为合数。
合数：合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数
你可能会说不就是求解质数吗？有什么难的,我三下五除二就给你解决了。只能说雀食是,对
于数据量较小的质数求解,我们分分钟搞定。但是如果我要求对于2-107以内的素数呢？这可
怎么办107的数据量特定要超时了呀。唉好不容易有一道会写的题还给超时了,真气人😈。
今天呢咱们就带大家学习一下,如何优美的求解出大数据量下的素数。
💟素数筛问题描述💞
将2~n之间所有的素数筛选出来,其中n<=10^6
样例输入：n 一个整数,作为筛选区间的右边界
样例输出：2-n之间的素数个数（包括n）
使用常规方法进行筛选的话会,如果数据规模较小还可以
如果数据规模较大就会很耗费时间。
可以大致分为一下几类：
新手筛(朴素筛)
新手优化筛
埃拉托斯特尼算法（常称为埃氏筛）
欧拉筛
测试数据分别为
新手筛 测试数据10^5 阶乘结果9592用时21.401952028274536s
新手优化筛 测试数据10^6 阶乘结果78498用时3.4318480491638184s
埃氏筛
测试数据10^6 阶乘结果78498用时0.27430033683776855s
测试数据10^7 阶乘结果664579用时2.836449384689331s
欧拉筛
测试数据10^6 阶乘结果78498 用时0.6881604194641113s
测试数据10^7 阶乘结果664579用时6.959389925003052s
由此间得,使用筛法可以大大的节约我们的时间,为什么一定要节约时间呢？
通常素数在问题求解中并不是核心算法,所以我们必须对其进行优化，以给核心算法争取更多的时间。🤤
💟新手筛💞
💙问题分析💙
入门的程序员就应该会,主要考察我们的编程小技巧。以及对素数的理解。😵💫
💙代码实现💙
import time n=int(1e6) ans=0 def sieve(n): for i in range(2,n): if n%i==0: return False return True start=time.time() for i in range(2,n): if sieve(i): ans+=1 end=time.time() print(f"阶乘结果{ans}用时{end-start}")
💟新手优化筛💞
💜问题分析💜
优化了一下代码,也就是对循环变量的终止条件开了个方。🥳
💜代码实现💜
import time n=int(1e6) ans=0 def sieve(n): for i in range(2,int(math.sqrt(n))+1): if n%i==0: return False return True start=time.time() for i in range(2,n): if sieve(i): ans+=1 end=time.time() print(f"阶乘结果{ans}用时{end-start}")
💟埃氏筛💞
🤍问题分析🤍
这里内层循环从ii开始是因为i~ii之间的合数总会被i之前的数筛选掉,剩余的都是质数。
没有必要对筛选过的再进行一遍筛选。利用这个性质可以知道当外层循环条件达到n的开方后
就可以筛选到整个序列2~n了,所以外层循环写到int(math.sqrt(n+1)即可，为了安全起见进行加1
不加总感觉可能会错，加了并不影响效率🧐
🤍代码实现🤍
import time n=int(1e6) ans=0 start=time.time() ans=[False]*(n+1) ans[0]=False ans[1]=True for i in range(2,int(math.sqrt(n+1)+1)): if not ans[i]: for j in range(i*i,n+1,i): ans[j]=True end=time.time() print(f"阶乘结果{n-sum(ans)}用时{end-start}")
💟欧拉筛（线性筛）💞
💗问题分析💗
埃氏筛重复筛到的数据比如30,既要被3进行筛掉,又要被5筛掉显然筛选重复了
欧拉筛加了一个判断条件，免去了筛除重复数据的步骤。👋
💗代码实现💗
import time n=int(1e6) ans=0 start=time.time() ans=[False]*(n+1) ls=[] ans[1]=True s=0 for i in range(2,n+1): if not ans[i]: ls.append(i) s=len(ls) for j in range(s): if i*ls[j] >n: break ans[i*ls[j]]=True if i%ls[j]==0: break end=time.time() print(len(ls),end-start)
