P1835

发表于 分类于
素数密度

素数密度

根号筛法。据说有低于线性的方法，但是我不会。

我们筛出 $[1,\sqrt R]$ 之间的素数，用这些素数取筛除 $[L,R]$ 中的合数。

为什么一定可以筛完？

显然一个合数可以用 $x=ab$ 表示。

那么不妨设 $a\le b$，那么就会有 $a^2\le ab=x$。即 $x$ 必有一个因子是 $\le \sqrt x$ 的。

然后就是一般筛法什么的了。

时间复杂度 $O(\sqrt R+\dfrac{\sqrt R}{\ln \sqrt R}\ln (R-L))$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;

const ll N=1e6;

ll n,ans,l,r,st,cnt;

ll prime[N+5];

bool f[N+5],ff[N+5];

void init() {
	f[1]=1;
	for(ll i=2;i<=n;i++) {
		if(!f[i]) prime[++cnt]=i;
		for(ll j=1;j<=cnt&&prime[j]*i<=n;i++) {
			f[prime[j]*i]=1;
			if(i%prime[j]==0) break;
		}
	}
}

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

void write(ll x) {
	static char buf[22];static ll len=-1;
	if(x>=0) {
		do{buf[++len]=x%10+48;x/=10;}while(x);
	}
	else {
		putchar('-');
		do{buf[++len]=-(x%10)+48;x/=10;}while(x);
	}
	while(len>=0) putchar(buf[len--]);
}

int main() {

	l=read();r=read();
	n=sqrt(r)+1;

	init();ans=r-l+1;

	for(ll i=1;i<=cnt;i++) {
		if(l<=prime[i]) st=l+l;
		else
		if(l%prime[i]==0) st=l;
		else st=l/prime[i]*prime[i]+prime[i];
		for(ll j=st;j<=r;j+=prime[i]) {
			if(!ff[j-l]) ans--;ff[j-l]=1;
		}
	}

	write(ans);
	
	return 0;
}