C++ 区间筛法解决

参考代码:

/*
 *找素数:区间筛法 
 *	同样用筛法,但不直接用在[0,b]上
 *	筛法的思想即筛去区间内素数的倍数,重复直到最大的素因子的倍数被筛去
 *而b的最大素因子为√￣b(根号b),所以我们可以用筛法在[2, √￣b]找到素数
 *的同时将[a,b]内的素数倍数筛去	 
 */
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

typedef long long ll;

const int Max_L = 1000000+1000; //[a,b] 
const int Max_N = (int)(sqrt(2147483647.0))+1000; //[2,√￣b]

ll a,b; //左右区间 
bool is_prime[Max_L+1]; //[a-a,b-a] is_prime[i] = true表示i为素数 
bool is_prime_small[Max_N]; //[2,√￣b] 内的素数

void segement_sieve();

int main()
{
	scanf("%lld%lld",&a,&b);
	
	segement_sieve();
	
	return 0;	
} 

void segement_sieve()
{
	/*初始化*/
	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;
	
	/*在得到[2,√￣b]内素数的同时筛去[a,b]内的素数的倍数*/
	for( int i=2; (ll)i*i<=b; i++ )
	{
		if( is_prime_small[i] )
		{//当前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;
			// a+i-1 / i : 如果 a==k*i -> 结果为k
			//				如果 k*i<a<(k+1)*i -> 结果为k+1 
		}
	}
	
	int ans = 0;
	for( int i=0; i<=b-a; i++ )
	{
		if( is_prime[i]	)	ans++;
	}
	printf("%d\n",ans);
}