kuai

用户名：kuai

访问量：5099

签　名：

等　　级
排　　名	4788
经　　验	1637
参赛次数	0
文章发表	10
年　　龄	0
在职情况	学生
学　　校	黄龙山职院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-夺宝奇兵-题解(C++代码)
浏览：590

蓝桥杯算法提高VIP-开灯游戏-题解-DFS模板题(C++代码)
浏览：479

蓝桥杯算法提高VIP-彩票-find()函数
浏览：274

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

蓝桥杯算法提高VIP-找素数-巨详细

　　作者: kuai　　　　发表时间：2020-04-19 11:32:24 浏览：1007　|　评论：1　

原题链接：蓝桥杯算法提高VIP-找素数

```cpp

/*
	分析：
		首先，判断素数，使用埃式筛法 
		其次，区间范围过大，不能用下标表示所有数字，
	思路：
		使用埃式筛法，筛出 [2,sqrt(R)] 中的素数，（因为一个数的最大质因子是 sqrt(x)） 
		再把这些素数，在 [L,R]区间内的倍数，给筛掉； 
*/

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MaxSize 1000002
using namespace std;
bool a[MaxSize];			// 筛 [2,sqrt(R)]，此时下标 i 表示 数字 
bool res[MaxSize];			// 筛 [L,R] 下标表示 i - L （ i 是实际想表示的数）  
size_t L,R;					// 区间 
int cnt;					// [L,R] 区间内的素数个数计数 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>L>>R;
	memset(a,true,sizeof(a));
	memset(res,true,sizeof(res));
	a[1] = false;			// false 表示不是素数 
	a[2] = true;			// true  表示  是素数

for(size_t i = 2;i * i <= R;++i ){
		// i 表示正在筛的数字，从 2 开始 
		if(a[i]){
			
		// 筛 [2,sqrt(R)] 
			//如果是素数，就把他的 整数倍的数 给筛掉 
			for(size_t j = 2;j * i <= sqrt(R);++j)
			// j 表示倍数，从 2 倍开始 
				a[i*j] = false;
				
		// 去除 [2,sqrt(R)] 区间内的素数在 [L,R] 区间内的整数倍的数字 
			//如果是素数，那么要把 其 在 [L,R] 内的整数倍的数给筛掉
			// 那么最小是 几倍 的数字 ， 会落在 [L,R] 区间内呢？
			// 倍数是 [ L / i ] 向上取整	
			for(size_t k = (L / i + (bool)(L % i));k * i <= R;++k){
				// k 表示倍数，注意向上取整的表示 
				if(k != 1)
				// 注意 倍数不能是 1 倍，否则会把原来的状态改变了 
				res[k * i - L] = false;
			}  
		}
		
	}
	
	// 最后统计一下 
	for(size_t j = 0;j <= R-L;++j){
		if(res[j])	
			++cnt;
	}
		
	cout<<cnt;
	
	return 0;
}
```

0.0分

54 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

盖亮

思路清晰

2022-02-09 13:27:35

kuai

TA的其他文章

你可能喜欢

C二级辅导-公约公倍（C语言代码）

拆分位数（C++代码）用char简单粗暴，嗯

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言考试练习题_保留字母（C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

蓝桥杯算法提高VIP-找素数-巨详细

评论区

精彩推荐

C语言训练-最大数问题（C语言代码）

九宫重排（C++代码）

C语言程序设计教程（第三版）课后习题9.1 （Java代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-数字母（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

kuai

TA的其他文章

你可能喜欢

C二级辅导-公约公倍 （C语言代码）

拆分位数 （C++代码）用char简单粗暴，嗯

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言考试练习题_保留字母 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

蓝桥杯算法提高VIP-找素数-巨详细

评论区

精彩推荐

C语言训练-最大数问题 （C语言代码）

九宫重排 （C++代码）

C语言程序设计教程（第三版）课后习题9.1 （Java代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-数字母 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C二级辅导-公约公倍（C语言代码）

拆分位数（C++代码）用char简单粗暴，嗯

C语言考试练习题_保留字母（C语言代码）

　　评论区

C语言训练-最大数问题（C语言代码）

九宫重排（C++代码）

C语言训练-数字母（C语言代码）