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

445 阅读 4 评论 2 点赞

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

如果一个数 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 人评分

本文分类：题解列表
浏览次数：445 次浏览
发布日期：2018-07-18 20:20:08
本文链接：https://blog.dotcpp.com/a/8293

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

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

评论列表共有 4 条评论

发表评论取消回复

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 4 条评论

发表评论 取消回复

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

评论列表共有 4 条评论

发表评论取消回复