UVA 10200 Prime Time 水

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1141

题意：判断区间[a,b]的f（i）是否为素数，f（i）=i*i+i+40；

思路：打个表，然后注意精度；

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define esp 1e-13
const int N=1e4+10,M=1e6+50000,inf=1e9+10,mod=1000000007;
int prime(int n)
{
    if(n<=1)
    return 0;
    if(n==2)
    return 1;
    if(n%2==0)
    return 0;
    int k, upperBound=n/2;
    for(k=3; k<=upperBound; k+=2)
    {
        upperBound=n/k;
        if(n%k==0)
            return 0;
    }
    return 1;
}
int f(int x)
{
    return x*x+41+x;
}
int flag[N];
int main()
{
    int x,y,i,z,t;
    for(i=0;i<=10000;i++)
    if(prime(f(i)))
    flag[i+1]=flag[i]+1;
    else
    flag[i+1]=flag[i];
    while(~scanf("%d%d",&x,&y))
    {
        double sum=flag[y+1]-flag[x];
        double di=(y-x+1);
        double ans=sum/di*100.0+1e-8;
        printf("%.2f
",ans);
    }
    return 0;
}