学步园

记录筛素数的板子。

AC代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

const int maxn = 4194304;
const int prin = 300000;

int prime[prin];
///仅包含奇数，isprime[k]代表2*k+3
bool isprime[maxn>>1];
int ptop = 0;

void sieve()
{
        memset(isprime, true, sizeof(isprime));
        prime[0] = 2;
        int sq = sqrt(maxn);
        for(int i = 3; i < maxn; i += 2)
        {
                if(isprime[(i-3)>>1])
                {
                        if(i <= sq+3)
                        {
                                for(int j = i*i; j < maxn; j += 2*i)
                                {
                                        isprime[(j-3)>>1] = false;
                                }
                        }
                        prime[++ptop] = i;
                }
        }
        return ;
}

int bin(int x)
{
        return (lower_bound(prime, prime+ptop+1, x) - prime);
}

int main()
{
        sieve();
        int n, m;
        while(~scanf("%d%d", &n, &m))
        {
        
                int tapn = bin(n);
                int tapm = bin(m);
                //cout << tapn << ' ' << tapm << endl;
                if(m == 2 || ((m&1) && isprime[(m-3)>>1]))
            tapm++;
        printf("%d\n", tapm-tapn);
        }
        return 0;
}