区间素数

给你两个整数a,b，求[a,b]区间内素数的个数

输入描述:

输入一行包含两个正整数a,b。

输出描述:

输出一个整数。

示例1
输入

350874129179 350875129179

输出

37682

qujiansushu.cppview raw

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int N = 1000010;
int mark[N+10], pmark[N+10];
typedef long long LL;

LL a, b;
void prime(){
    int n = sqrt(b);
    for(int i=2;i<=n;i++)
        if(!mark[i]){
            for(int j=i+i;j<=n;j+=i)
                mark[j] = 1;
            LL p;
            if(a%i==0) p = a;
            else p = max(2LL, (a/i + 1) * i);
            for(; p<=b; p+=i) pmark[p-a] = 1;
        }
}

int main(){
    scanf("%lld%lld", &a, &b);
    prime();
    int sum = 0;
    for(int i=0;i<=b-a;i++)
        if(pmark[i]==0) sum++;
    if(a==1) sum--;
    printf("%d\n", sum);
    return 0;
}