区间内的素数个数判定

问题一：

给定整数n，求n以内有多少个素数

分析：
应用筛选法，其核心思想就是，首先将2~n范围内的所有整数写出来。其中最小的数字2是素数，将表中所有2的倍数都划去。表中剩余的最小的数字是3，它不能被更小的整数除，所以它是素数，再将表中所有的3得倍数都划去。以此类推，如果表中剩余的数字是m的话，m就是素数，然后再将所有的m的倍数划去。

#include<iostream>
#include<stdio.h>
using namespace std;
int prime[1000009];///保存素数
bool is_prime[1000009];///表示i是不是素数

int sieve(int n)
{
    int ans=0;
    for(int i=0;i<=n;i++)
        is_prime[i]=true;
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=n;i++)
    {
        if(is_prime[i])
        {
            prime[ans++]=i;
            for(int j=2*i;j<=n;j+=i)
                is_prime[j]=false;
        }
    }
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d
",sieve(n));
    return 0;
}

问题二：

求一个特定的区间 (a<=x<b) 内的素数的个数

#include<iostream>
#include<stdio.h>
typedef long long ll;
using namespace std;
bool is_prime_small[1000009];
bool is_prime[1000009];
///对区间[a,b)内的整数进行筛选。 is_prime[i-a]=true <=> i是素数

void segment_sieve(ll a,ll b)
{
    for(int i=0;(ll)i*i<b;i++)
        is_prime_small[i]=true;
    for(int i=0;i<b-a;i++)
        is_prime[i]=true;
    for(int i=2;(ll)i*i<b;i++)
        if(is_prime_small[i])
        {
            for(int j=2*i;(ll)j*j<b;j+=i)
                is_prime_small[j]=false;
            for(ll j=max(2LL,(a+i-1)/i)*i;j<b;j+=i)
                is_prime[j-a]=false;
        }
}
int main()
{
    ll a,b,c;
    scanf("%lld%lld",&a,&b);
    segment_sieve( a, b);
    int ans=0;
    c=b-a;
    for(int i=0;i<c;i++)
    {
        if(is_prime[i]) ans++;//cout<<i+a<<" ";
    }
    if(a==1) ans--;
    printf("%d",ans);
    return 0;
}