AKOJ-1695-找素數

題意：

給定區間L，R。

計算區間中素數個數。

2 <= L,R <= 2147483647, R-L <= 1000000。

思路：

素數區間篩

先篩(2-sqrt(r))。

再用(2-sqrt(r))中的素數篩(l-r)。

代碼:

1.自己寫的區間篩，將篩2-sqrt（r) 分開了。

#include <iostream>
#include <string>
#include <queue>
#include <memory.h>
#include <math.h>
using namespace std;
typedef long long LL;
const int MAXN = 1000010;
int isPrimersmall[MAXN];
int isPrimer[MAXN];int main()
{LL l,r;scanf("%lld%lld",&l,&r);isPrimersmall[0] = 1;isPrimersmall[1] = 1;int x = sqrt(r);for (int i = 2;i<=x;i++){if (isPrimersmall[i] == 0){for (int j = i * i; j <= x; j += i)isPrimersmall[j] = 1;}}for (int i = 2;i<=x;i++){if (isPrimersmall[i] == 0){for (int j = (int)((l + (i-1))/ i) * i;j <= r; j += i){if (j != i)isPrimer[j-l] = 1;}}}int sum = 0;for (int i = 0;i<=r-l;i++){if (isPrimer[i] == 0)sum++;}printf("%d\n",sum);return 0;
}

　　

2.將篩(2-sqrt(r))和(l-r)放在一起篩。

#include <iostream>
#include <string>
#include <queue>
#include <memory.h>
#include <math.h>
using namespace std;
typedef long long LL;
const int MAXN = 1000010;
int isPrimersmall[MAXN];
int isPrimer[MAXN];int segement_sieve(LL a,LL b)
{for (LL i = 0;i*i <= b;i++)isPrimersmall[i] = 1;for (LL i = 0;i <= b-a;i++)isPrimer[i] = 1;for (LL i = 2;i*i <= b;i++){if (isPrimersmall[i]){for (LL j = i*2;j*j <= b;j+=i)isPrimersmall[j] = 0;for (LL j = max(2LL,(a+i-1)/i) * i;j <= b ;j+=i)isPrimer[j-a] = 0;}}int sum = 0;for (int i = 0;i <= b-a;i++)if (isPrimer[i])sum++;return sum;
}int main()
{LL a,b;scanf("%lld%lld",&a,&b);printf("%d\n",segement_sieve(a,b));return 0;
}