素數篩(1) 埃氏篩法，素數
其原理就是先將2-n之內的所有數存在一個數組裡，初始化所有數全為素數，然後從2開始尋找，只要標記是素數便將他的所有倍數的標記都改為合數，依次類推。時間復雜度為O（nloglogn）。
代碼實現
![]()
1 void prime_table()
2 {
3 for(int i=2;(LL)i<=n;i++) prime[i]=1;
4 for(int i=2;(LL)i*i<=n;i++)
5 if(prime[i]) for(LL j=i*i;j<=n;j+=i) prime[j]=0;
6 }
素數篩
區間素數篩
當要求的范圍過大時，上述方法會爆內存，所以我們可以先做好【2，√b）和【a，b）的表，在篩【2，√b）的同時將其倍數在【a，b）中劃去。
40027120區間內素數的個數
難度級別：B； 運行時間限制：1000ms； 運行空間限制：262144KB； 代碼長度限制：2000000B
試題描述
給定兩個正整數 a 和 b，請你統計區間 [a，b) 內有多少個素數。
輸入
共一行包含兩個正整數 a 和 b，用一個空格分隔開。
輸出
一個數，表示所給區間內的素數的個數。
輸入示例
22 37
輸出示例
3
其他說明
數據范圍：1≤ a < b ≤ 10^12 ， b-a ≤ 10^7 。
樣例說明：有23、 29 和 31 共 3 個素數。
![]()
1 #include<iostream>
2 using namespace std;
3 #define LL long long
4 LL read()
5 {
6 LL x=0,f=1;
7 char c=getchar();
8 while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
9 while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
10 return x*f;
11 }
12 #define maxn 1000010
13 bool prime[maxn], is[maxn];
14 LL a, b;
15 void prime_table()
16 {
17 for(int i = 2; (LL)i * i < b; i++) prime[i] = 1;
18 for(int i = 0; i < b - a; i++) is[i] = 1;
19 for(int i = 2; (LL)i * i < b; i++) if(prime[i]) {
20 for(LL j = 2 * i; j * j < b; j += i) prime[j] = 0;
21 for(LL j = max(2LL, (a + i - 1) / i) * i; j <= b; j += i) if(j >= a) is[j-a] = 0;
22 }
23 return ;
24 }
25
26 int main()
27 {
28 a = read(); b = read();
29 prime_table();
30 int cnt = 0;
31 for(int i = 0; i < b - a; i++) if(is[i]) cnt++;
32 if(a == 1) cnt--;
33 printf("%d\n", cnt);
34
35 return 0;
36 }
View Code
