学步园

       跟判断素数有关的题。题意：有这样一个公式，n^2 + n + 41，当0 <= n <= 39时这个公式的值都是素数，但是n > 39时这个公式的值有可能不是素数了，不过已知n <= 10000000时这个公式的值有47.5%的素数。现在给你区间的左右端点a和b（0 <= a <= b <= 10000），请你写个程序判断一下在当n在[a, b]区间内这个公式生成的值是素数的个数占这个区间大小的百分比。

       我的解题思路：反正n = 10000时公式的值还没有超过int范围，先将10002以内范围的素数都筛出来，然后用来判断区间内公式的值是否为素数，反正也就最多10000次判断，存储为前缀和的形式，最后根据输入的左右端点直接输出就行了。注意：比较坑的是四舍五入的地方，浮点数的话其实是要大于五才会入，小于等于五还是舍。这里要处理好。

       我的解题代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>

using namespace std;

const int N = 10003;

bool isprime[N];
int primes[N], pn;
int prmnum[N];      //prmnum[x]表示当n在[0, x)区间内公式能生成多少个素数，prmnum[0]特殊
int l, r;

void InitRead();

void DataProcess();

void FastSieve(int maxn);

inline int fun(int x)
{
    return x * x + x + 41;
}

int main()
{
    InitRead();
    while (~scanf("%d %d", &l, &r))
    {
        DataProcess();
    }
    return 0;
}

void InitRead()
{
    memset(isprime, true, sizeof(isprime));
    memset(prmnum, 1, sizeof(prmnum));
    isprime[0] = isprime[1] = false;
    pn = 0;
    FastSieve(N - 1);
    for (int i=0; i<=40; ++i) prmnum[i] = i;    //已知[0, 39]区间内公式生成的值都是素数
    for (int i=40; i<N; ++i)
    {
        prmnum[i+1] = prmnum[i] + 1;
        int temp = fun(i);
        for (int j=0; j<pn; ++j)    //朴素素性测试
        {
            if (primes[j] * primes[j] > temp) break;
            if (temp % primes[j] == 0)
            {
                prmnum[i+1] = prmnum[i];
                break;
            }
        }
    }
    return;
}

void DataProcess()
{
    char str[10];
    double ans;
    sprintf(str, "%lf\n", (double)(prmnum[r+1] - prmnum[l]) / (double)(r - l + 1) * 100);
    sscanf(str, "%lf", &ans);
    if (str[2] == '.' && str[5] >= '5') ans += 0.001;   //特殊处理，四舍五入
    printf("%.2lf\n", ans);
    return;
}

void FastSieve(int maxn)
{
    for (int i=2; i<=maxn; ++i)
    {
        if (isprime[i]) primes[pn++] = i;
        for (int j=0; j<pn; ++j)
        {
            if (i * primes[j] > maxn) break;
            isprime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
    return;
}