HzuWHF

用户名：I7I08I9047

访问量：76444

签　名：

我RUN了

等　　级
排　　名	18
经　　验	20461
参赛次数	13
文章发表	127
年　　龄	3
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-组合公式求值（C++代码）
浏览：1619

蓝桥杯算法提高VIP-金陵十三钗（C++代码）（状压Dp）
浏览：813

文艺平衡树（Splay）
浏览：684

你可能喜欢

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

小O的质数（C++代码）

　　作者: HzuWHF　　　　发表时间：2018-07-18 20:20:08 浏览：392　|　评论：2　

原题链接：小O的质数

更新一下吧，我都看不懂我以前写的什么。

如果一个数 N 是合数，那么至少能被 √N 内的某一个数整除。
所以要筛选到 R 范围内的素数，只需要用 √R 内的素数，用埃氏筛的思想筛出区间内的合数，这些合数可以用 √R 内的素数乘以某个整数得到，那剩下没有被筛去的便是质数了。

```cpp
constexpr auto Inf = 0X3F3F3F3F;
#ifndef LOCAL
	#include <bits/stdc++.h>
#endif
typedef long long LL;
using namespace std;

namespace IO {
	inline LL read() {
		LL o = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
		return o * f;
	}
	inline char recd() {
		char o; while ((o = getchar()) != 'C' && o != 'D'); return o;
	}
}
using namespace IO;

const int SIZE = 1E6 + 3;
int p[SIZE], v[SIZE], Ind, d[SIZE];

void pre(int N) {
	for (int pos = 2; pos <= N; pos++) {
		if (!v[pos]) p[++Ind] = pos;
		for (int u = 1; u <= Ind && pos * p[u] <= N; u++) {
			v[pos * p[u]] = 1;
			if (pos % p[u] == 0) break;
		}
	}
}

int main() {
	pre(sqrt(1E9) + 7);
	int L, R;
	while (~scanf("%d%d", &L, &R)) {
		memset(d, 0, sizeof d);
		int LIM = sqrt(R);
		for (int u = 1; p[u] <= LIM && u <= Ind; u++) 
			for (int b = max(int(ceil(1.0 * L / p[u])), 2); b * p[u] <= R; b++)
				d[b * p[u] - L] = 1;
		int ans = 0;
		for (int pos = L; pos <= R; pos++)
			ans += !d[pos - L];
		printf("%d\n", ans);
	}
}

```

以前写的在题号1525那边。

0.0分

3 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

UDP广播协议叫吃饭

大佬教我数论

2019-06-07 00:21:49

CtrlCV工程师

思路正确，理解的很棒，不过这个筛素数的办法太笨了点，建议学习一下O(nlogn)或者O(n)的更棒的筛法

2018-09-15 13:43:55

HzuWHF

TA的其他文章

你可能喜欢

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

【计算球体积】（C语言代码）

点我有惊喜！你懂得！

C语言训练-求函数值（C语言代码）

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

小O的质数（C++代码）

评论区

精彩推荐

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简单的a+b （C语言代码）

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

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

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

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

杨辉三角（C语言代码）

sizeof的大作用（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-大、小写问题（C语言代码）

HzuWHF

TA的其他文章

你可能喜欢

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

【计算球体积】 （C语言代码）

点我有惊喜！你懂得！

C语言训练-求函数值 （C语言代码）

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

小O的质数 （C++代码）

评论区

精彩推荐

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简单的a+b （C语言代码）

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

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

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

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

杨辉三角 （C语言代码）

sizeof的大作用 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-大、小写问题 （C语言代码）

【计算球体积】（C语言代码）

C语言训练-求函数值（C语言代码）

小O的质数（C++代码）

　　评论区

杨辉三角（C语言代码）

sizeof的大作用（C语言代码）

C语言训练-大、小写问题（C语言代码）