TreeMind树图在线AI思维导图
当前位置:树图思维导图模板高校与高等教育高等数学求n以内的素数-从入门到入坟思维导图

求n以内的素数-从入门到入坟思维导图

  收藏
  分享
免费下载
免费使用文件
U125568174 浏览量:2182023-02-09 20:24:33
已被使用49次
查看详情求n以内的素数-从入门到入坟思维导图

数学知识

树图思维导图提供 求n以内的素数-从入门到入坟 在线思维导图免费制作,点击“编辑”按钮,可对 求n以内的素数-从入门到入坟  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:31b67158364f0a9dfc7fd0cacfe9954d

思维导图大纲

求n以内的素数 -从入门到入坟思维导图模板大纲

1、试除法

最简单的方法,对n以内所有数进行试除

要点

1、开始前判断是否大于1,不满足直接退出,因为0,1不是素数

2、for循环内条件写i*i<=n,减少不必要的判断,比sqrt()省时间

bool prime(int x){ if(x<=1) return 0; for(int i=2;i*i<=n;i++){ if(x%i==0) return 0; } return 1; }

缺点

每一个素数都要进行较长的计算,费时间

由于n以内素数约为n/ln(n)个,所以时间复杂度为O(n*sqrt(n)/ln(n)), 较为费时间

2、朴素筛

原理

将所有数的n倍(n≥2)全部删除,因为他们一定不是素数

for(int i=2;i<=n;i++){ for(int j=2;i*j<=n;j++){ book[i*j]=1; } }

时间复杂度略有降低,约n*log2(n)

缺点

需要对每一个数的倍数筛除,即使是合数的倍数,极其浪费时间

例如12=2*6=3*4,则它被筛了4次

3、埃氏筛

在朴素筛的基础上加入一条判断条件以及第二重循环小优化

for(int i=2;i<=n;i++){ if(book[i]==0){ for(int j=i;i*j<=n;j++){ book[i*j]=1; } } }

时间复杂度大大降低,约为O(NlnlnN),已经接近于O(N)级别

缺点

例如12=2*4=2*6,则12总计被筛了两次,以此类推

4、欧拉筛(线性筛)

由于埃氏筛任由重复运算,其实并不是最快

欧拉筛将素数存储在数组中,第二重循环将i的prime[j]倍的数筛除,同时当i是prime[j]的倍数是退出循环。保证每个合数只计算一次

for(int i=2;i<=n-1;i++){ if(book[i]==0){ cnt++; prime[cnt]=i; } for(int j=1;prime[j]*i<n;j++){ book[i*prime[j]]=1; if(i%prime[j]==0) break; } }

因其对每一个合数只会筛除一次,时间复杂度为O(n),目前最快的筛法

相关思维导图模板

 义务教育数学课程标准思维导图

树图思维导图提供 义务教育数学课程标准 在线思维导图免费制作,点击“编辑”按钮,可对 义务教育数学课程标准  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:c0e5175a23b28f2d93641c2ad873a528

六年级数学《百分数》思维导图

树图思维导图提供 六年级数学《百分数》 在线思维导图免费制作,点击“编辑”按钮,可对 六年级数学《百分数》  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:c241e841b4226800de5b08c6d27b79c5