洛谷P1835 素数密度

素数密度

题目背景

UPD:

2024.8.12：加入一组 Hack 数据。

题目描述

给定 $L, R$ ，请计算区间 $[L, R]$ 中素数的个数。

$1\leq L\leq R < 2^{31}$ ， $R-L\leq 10^6$ 。

输入格式

第一行，两个正整数 $L$ 和 $R$ 。

输出格式

一行，一个整数，表示区间中素数的个数。

样例 #1

样例输入 #1

2 11

样例输出 #1

题目分析：开始想到了欧拉筛法，但交上去发现wa只得了40分，了于是看数据范围发现然而我们并不能筛到 2e9,空间上也不允许，想想办法，因为2e9范围内的质数因子最大也到不了50000(用计算器或者代码sqrt一下2∼50000以内的素数，然后对于每一个数，筛出质因子的倍数，剩下的就是区间内的质数啦。

数学知识储备
【大于L,并且是p的倍数,最小整数是多少?】

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int main() {
    //数学知识储备
    //【大于等于L,并且是p的倍数,最小整数是多少?】
    int p = 3;
    for (LL L = 100; L <= 200; L++)
        cout << max(2ll, (L - 1) / p + 1) * p << endl;
    return 0;
}

最后奉上代码部分：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

int primes[N];//存储所有素数 
bool vis[N],a[N];//vis存储i是否被筛掉 
//数组a记录偏移后的数据是不是合数，1：合数；0：质数。a[i]表示l+i是不是合数, 有一个偏移量l
ll l,r; 
int cnt; 
 
void get_primes()
{
	cnt = 0;
	for(int i = 2; i <= 50000; i++)
	{
		if(!vis[i]) primes[cnt++] = i;
		for(int j = 0; primes[j] <= 50000 / i; j++)
		{
			vis[primes[j] * i] = true;
			if(i % primes[j] == 0) break;
		}
	}
}

ll read()
{
	ll s=0,f=1;
	char ch=getchar();
	
	while (ch<'0'||ch>'9')
	{
   	   if (ch=='-') f=-1;
	   ch=getchar();
	}
	while (ch>='0'&&ch<='9')
	{
	   s=s*10+ch-'0';
	   ch=getchar();
	}
	return s*f;
}


int main() {
   
    l = read(),r = read();
    
    l = l == 1 ? 2 : l;
    
    get_primes();
    
    for(int i = 0; i < cnt; i++)
    {
    	ll st = max(2ll,(l-1) / primes[i] + 1) * primes[i];
    	for(ll j = st; j <= r; j += primes[i]) a[j - l] = true;
	}
	
    //区间范围,因为我们无法完全映射所有的区间，只能采用类似于偏移的办法对某段区间整体偏移l进行描述。
	int ans = 0;
    for (ll i = l; i <= r; i++) if (!a[i - l])ans++;
    printf("%d", ans);
    
    return 0;
}