【2024.9.30练习】素数密度

题目描述

---

题目分析

由于是区间内筛选素数，考虑用埃氏筛法。总区间长度为，埃筛的长度即为。

注意这里的，这说明区间内的数字最多有个。

---

我的代码

一开始使用的int类型，但是即便数据都在Int范围内，但由于R的值太接近Int边界，在判定i*i是否大于R等乘法表达式时很可能造成溢出，因此区间筛法尽量还是使用long long存储数据。

另外一个难点是筛选区间的素数时，变量j的起点值为。初见很难推导出来。

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
const int MAX_N = 1000005;
int is_p[MAX_N];	//2到根号R区间
int is_p_ans[MAX_N];	//L到R区间int main() {//初始化ll L;ll R;cin >> L >> R;for (ll i = 0; i < MAX_N; i++){is_p_ans[i] = 1;is_p[i] = 1;}//max_i=根号R（向下取整）ll max_i;for (ll i = 1; (ll)i * i <= R; i++){max_i = i; }//cout << max_i << endl;//埃筛for (ll i = 2; i <= max_i; i++){if (is_p[i] == 1) {for (ll j = i * 2; j <= max_i; j += i){is_p[j] = 0;	//筛[2,√R]}for (ll j = max(2LL, (L + i - 1) / i) * i; j <= R; j += i) {is_p_ans[j - L] = 0;	//筛[L,R]}}}//统计int ans = 0;for (int i = 0; i <= R-L; i++){if (is_p_ans[i] == 1) {cout << i + L << endl;ans++;}}if (L == 1) {ans--;}cout << ans;return 0;
}