codevs 3223 素数密度

题目描述 Description

给定区间[L, R](L <= R <= 2147483647，R-L <= 1000000)，请计算区间中素数的个数。

输入描述 Input Description

两个数L和R

输出描述 Output Description

一行，区间中素数的个数

样例输入 Sample Input

2 11

样例输出 Sample Output

5

数据范围及提示 Data Size & Hint

详见试题

#include<cstdio>

#include<iostream>

#include<cmath>

using namespace std;

int l,r,f[1100000]={0},a[1100000],ans=0;//重要的事情说三遍，数组开大点，数组开大点，数组开大点！（找了一晚上错误，就是找不到错误，马丹，最后发现数组开小了，明明我是卡着点开的数组）

int su(int x)

{

	if (x==2)  return 1;

	for (int i=2;i<=ceil(sqrt(x));i++)

	  if (x%i==0) return 0;

	return 1;

}//判断是不是素数

void pc(int x)

{

	int q=l/x;

	int s=l%x;

	int h=r/x;

	for (int j=0;j<=h-q;j++)

	   f[x-s+x*j]=1;

    if (q==0)

      f[x-s]=0;

    if (q>1&&s==0)

      f[0]=1;

}//筛子，筛掉所有素数的倍数

int main()

{

   scanf("%d%d",&l,&r);

   for (int i=0;i<=r-l;i++)

     a[i]=l+i;

   for (int i=2;i<=ceil(sqrt(r));i++)

      if (su(i)) pc(i);

   if (a[0]==0||a[0]==1)

     f[0]=1;

    if (a[1]==0||a[1]==1)

      f[1]=1;

   for (int i=0;i<=r-l;i++)

     if (not f[i])

	   ans++;

    printf("%d",ans);

    return 0;

}