Description

小X 是一位熱愛數學的男孩子，在茫茫的數字中，他對質數更有一種獨特的情感。小X 認為，質數是一切自然數起源的地方。
在小X 的認知里，質數是除了本身和1 以外，沒有其他因數的數字。
但由于小X 對質數的熱愛超乎尋常，所以小X 同樣喜歡那些雖然不是質數，但卻是由兩個質數相乘得來的數。
于是，我們定義，一個數是小X 喜歡的數，當且僅當其是一個質數，或是兩個質數的乘積。
而現在，小X 想要知道，在L 到R 之間，有多少數是他喜歡的數呢？

Input

第一行輸入一個正整數Q，表示詢問的組數。
接下來Q 行。包含兩個正整數L 和R。保證L≤R。

Output

輸出Q 行，每行一個整數，表示小X 喜歡的數的個數。

Sample Input

輸入1：

1
1 6

輸入2：

10
282 491
31 178
645 856
227 367
267 487
474 697
219 468
582 792
315 612
249 307

輸入3：

10
20513 96703
15236 86198
23185 78205
40687 48854
42390 95450
63915 76000
36793 92543
35347 53901
44188 76922
82177 90900

Sample Output

輸出1：

5

樣例1解釋：

6以內的質數有2,3,5，而4=2*2,6=2*3。因此2,3,4,5,6都是小X 喜歡的數，而1 不是。

輸出2：

97
78
92
65
102
98
114
90
133
29

輸出3：

24413
23001
17784
2669
16785
3833
17712
6028
10442
2734

Data Constraint

Solution

• 做法比較顯然，首先線篩出質數來，

• 接著枚舉兩個質數（乘積大于 107 就退出），把其乘積也篩了。

• 于是我們就得到一個判斷一個數是否合法的布爾數組。

• 那么要求一個區間，就做一遍前綴和即可。

Code

#include<cstdio> using namespace std; const int N=1e7+1; int f[N]; bool bz[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } int main() {for(int i=2;i<N;i++){if(!bz[i]) f[++f[0]]=i;for(int j=1;j<=f[0] && i*f[j]<N;j++){bz[i*f[j]]=true;if(i%f[j]==0) break;}}for(int i=1;i<=f[0];i++)for(int j=1;j<=f[0] && f[i]*f[j]<N;j++) bz[f[i]*f[j]]=false;f[0]=f[1]=0;for(int i=2;i<N;i++) f[i]=f[i-1]+(!bz[i]);int q=read();while(q--){int l=read(),r=read();write(f[r]-f[l-1]),putchar('\n');}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5458. 【NOIP2017提高A组冲刺11.7】质数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。