【JZOJ 5458】素数【数論、数学】

タイトルの大意:
テーマリンク:https://jzoj.net/senior/#main/show/5458 テーマ画像:http://wx4.sinaimg.cn/mw690/0060lm7Tly1fweob4u4hmj30j50ba0t1.jpg http://wx3.sinaimg.cn/mw690/0060lm7Tly1fweob4u5lfj30jp0gr3yu.jpg http://wx2.sinaimg.cn/mw690/0060lm7Tly1fweob4unxlj30ji0fqjsx.jpg
L-LからR R Rの質数または2つの素数の積の数を求めます。
考え方:
まず、最大データを観察します。L≦R≦1 0 7、Q≦1 0 L\leq R\leq 10^7、Q\leq 10^5 L≦R≦107、Q≦105は必ずオフラインします。まず素数をふるいます。1からR R Rまでの素数だけでなく、 も得られます。それなら、1つの数x x x xに対して。

素数であれば、明らかにa n s++ans++

素数でない場合：

この数の最小素因数v[x]v[x]v[x]v[x]を知っていますが、もしそれが問題の要求に符合すれば、必ずx=p r i m e[i]があります。× p r＿i m e[j]x=preme[i]\times preme[j]x=preme[i]×preme[j]。v[x]v[x]v[x]v[x]で素数も知っていますから、題意に合うなら、x=v[x]があります。× p r＿i m e[j]x=v[x]\times preme[j]x=v[x]×preme[j]は、p r＿i m e[j]=x÷v[x]preme[j]=x\div[x]preme[j]=x÷v[x]です。したがって、x÷v[x]x\div[x]x÷v[x]が素数であれば、a n s++ans++

そうでないと合法的ではないです。

それでは、プレフィックスとs s、s[i]s[i]s[i]は、1からR R Rまでの間にどれだけの要求に合致するかを示す数を求めることができる。そしてO（1）O（1）O（1）で答えます。時間複雑度：O（1 0 7）O（10^7）O（107）（固定値は、O（R）O（R）O（R）O（R））））です。
コード:

#include 
#include 
#define N 10000100
#define MAXN 10000000
#define ll long long
using namespace std;

int sum,v[N],prime[N],s[N],l,r,n;
bool isp[N];

int f;
char c;

int read()  //   
{
	c=getchar();
	f=0;
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') 
	{
		f=f*10+(c-'0');
		c=getchar();
	}
	return f;
}

int write(int x)  //   
{
	if (x>9) write(x/10);
	putchar(x%10+48);
}

void find()
{
	for (int i=2;i<=MAXN;i++)  //   
	{
		if (!v[i])
		{
			v[i]=i;
			prime[++sum]=i;
			isp[i]=1;
		}
		for (int j=1;j<=sum;j++)
		{
			if (prime[j]>MAXN/i) break;
			if (prime[j]>v[i]) break;
			v[i*prime[j]]=prime[j];
		}
	}
	for (int i=2;i<=MAXN;i++)
	 if (isp[i]||isp[i/v[i]])  //    
	  s[i]=s[i-1]+1;
	 else s[i]=s[i-1];
}

int main()
{
	find();
	n=read();
	while (n--)
	{
		l=read();
		r=read();
		write(s[r]-s[l-1]);
		putchar(10);
	}
	return 0;
}