2018-03-08 素数筛选

// 埃氏筛法
//  小范围的求解素数 su[i]保存第i个素数，下标是从1开始
#define MAX 100000    //求MAX范围内的素数
long long su[MAX],cnt;
bool isprime[MAX];
void prime()
{
    cnt=1;
    memset(isprime,1,sizeof(isprime)); //初始化认为所有数都为素数
    isprime[0]=isprime[1]=0;  //0和1不是素数
    for(long long i=2;i<=MAX;i++)
    {
        if(isprime[i])
            su[cnt++]=i;//保存素数i 下标是从1开始
        for(long long j=1;j<cnt&&su[j]*i<MAX;j++)
        {
            isprime[su[j]*i]=0;//筛掉小于等于i的素数和i的积构成的合数
        }
    }
}

//求一个特定的区间 (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;
}

//不是很懂这种筛法 这个比上面优化一些

const int N = 1000000 + 5;
int prime[N], check[N];

memset(prime, 0, sizeof(prime));
memset(check, 0, sizeof(check));
int ptot = 0;
for(int i = 2; i <= n; i ++){
    if(!check[i]) prime[ptot ++] = i;
    for(int j = 0; j < ptot; j ++){
        if(prime[j] * i > n) break;
        check[prime[j] * i] = 1;
        if(i % prime[j] == 0) break;
    }
}