数与运算-埃氏筛 P1835 素数密度

P1835 素数密度
数与运算-埃氏筛
题目来源-洛谷题库

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
typedef long long LL;
bool is_prime[maxn + 5], check[1000009];//根号n内的质数表和 
vector<long long> p;

void init() // 埃氏筛预处理1e5范围内的素数
{
    is_prime[0] = is_prime[1] = true;

    for (LL i = 2; i <= maxn; i++)
    {
        if (!is_prime[i])
        {
            p.push_back(i);
            for (LL j = i * i; j <= maxn; j += i)//每次都从其i*i倍开始 
                is_prime[j] = true;
        }
    }
}

int main()
{
    init();
    LL l, r;
    cin >> l >> r;
	//开始用质数表筛掉l-r区间的合数 
    for (int i = 0; i < p.size(); i++) 
    {
    			//直接从L-R区间内最小的p[i]的倍数开始筛，
				//第一种情况：p[i]*p[i]<L（舍去，找>L的 倍数） 
				//第二种情况p[i]*p[i]远大于L-说明L- p[i]*p[i]都是筛过的或者都是质数 
        LL x = max(p[i] * p[i], (l + p[i] - 1) / p[i] * p[i]);
        for (LL j = x; j <= r; j += p[i])
            check[j - l] = true;//通过映射 直接映射：处理 j(对应j-l) 节约空间 
    }
    //特判数据是1 的情况 
    if(l == 1) check[0] = true;
    int cnt = 0;
    //计算最终结果 
    for (int i = l; i <= r; i++)
    {
        if (!check[i - l])
            cnt++;
    }
    cout << cnt;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
typedef long long LL;
bool is_prime[maxn + 5], check[1000009];//根号n内的质数表和
vector p;

void init() // 埃氏筛预处理1e5范围内的素数
{
is_prime[0] = is_prime[1] = true;

for (LL i = 2; i <= maxn; i++)
{
    if (!is_prime[i])
    {
        p.push_back(i);
        for (LL j = i * i; j <= maxn; j += i)//每次都从其i*i倍开始 
            is_prime[j] = true;
    }
}

}

int main()
{
init();
LL l, r;
cin >> l >> r;
//开始用质数表筛掉l-r区间的合数
for (int i = 0; i < p.size(); i++)
{
//直接从L-R区间内最小的p[i]的倍数开始筛，
//第一种情况：p[i]*p[i]<L（舍去，找>L的 倍数）
//第二种情况p[i]*p[i]远大于L-说明L- p[i]*p[i]都是筛过的或者都是质数
LL x = max(p[i] * p[i], (l + p[i] - 1) / p[i] * p[i]);
for (LL j = x; j <= r; j += p[i])
check[j - l] = true;//通过映射 直接映射：处理 j(对应j-l) 节约空间
}
//特判数据是1 的情况
if(l == 1) check[0] = true;
int cnt = 0;
//计算最终结果
for (int i = l; i <= r; i++)
{
if (!check[i - l])
cnt++;
}
cout << cnt;
return 0;
}