没有合适的资源?快使用搜索试试~ 我知道了~
经典的素数筛算法学习笔记
需积分: 15 1 下载量 55 浏览量
2022-04-02
08:45:55
上传
评论 1
收藏 11.59MB PDF 举报
温馨提示
试读
9页
包含了素数筛和线性筛算法的实现和理解,是很实用的一种筛选算法, 筛选算法的本质是一种标记算法
资源详情
资源评论
资源推荐
简单的素数筛选的几种方式:
//第一种(说是筛选)其实就是暴力枚举:
时间复杂度: O(N*logN) 不是那么的好
上代码:
//于是乎还是来了个空间换时间的一个素数筛算法:
版本1:
//有人说,哎,这个好啊,可是这样通过素数来标记合数,然后通过素数来标记合数,最后就判读标记输出下标
合数就可以了.但是这样其实还不是很让我满意,咋了我只能写到这一步吗?? 可不可以就是不用整个容
器的全部遍历一遍,只是简单的遍历素数就OK了,当然要安排
//第一种方式,暴力的进行一个枚举所有情况
//不是很好,时间复杂度太高了O(n^2)了
int getPrime(int prime[])
{
int cnt = 0;
for (int i = 2; i < MAX_N; i++){
bool flag = true; //标记素数
for (int j = 2; j * j <= i; j++) {
if (i % j == 0) {
flag =false; //不是素数,修改标记;
break;
}
}
if (flag) prime[cnt++] = i; //存储素数;
}
return cnt;
}//太垃圾了,对于一些拉跨的人是够了,但是优质的程序员如何能忍
int getPrime1(int prime[]){
int cnt = 0;
for (int i = 2; i < MAX_N; i++) {
if (prime[i]) continue; //是合数就跳过
cnt++; //没有跳过素数++
for (int j = 2 * i; j < MAX_N; j += i) {
prime[j] = true; //标记合数;
}
}
return cnt;
}
int getPrime2(int prime[]) {
int cnt = 0;
for (int i = 2; i < MAX_N; i++) {
if (prime[i]) continue;
prime[cnt++] = i; //直接的将素数存入数组容器的前面,然后只用遍历前面其实得到的就
是素数了.
for (int j = 2 * i; j < MAX_N; j += i) {
prime[j] = true; //合数;
}
小杰312
- 粉丝: 1w+
- 资源: 12
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0