Prime Time UVA – 10200（精度处理，素数判定）

　　PrimeTimeUVA-10200（精度处理，素数判定）

 

　　ProblemDescription

 

　　Eulerisawell-knownmatematician,and,amongmanyotherthings,hediscoveredthattheformula

 

　　n^{2}+n+41n2+n+41producesaprimefor0≤n&lt;400≤n<40.Forn=40n=40,theformulaproduces16811681,whichis41∗4141∗41.Eventhoughthisformuladoesn’talwaysproduceaprime,itstillproducesalotofprimes.It’sknownthatforn≤10000000n≤10000000,thereare47,547,5%ofprimesproducedbytheformula!So,you’llwriteaprogramthatwilloutputhowmanyprimesdoestheformulaoutputforacertaininterval.

 

　　Input

 

　　Eachlineofinputwillbegiventwopositiveintegeraaandbbsuchthat0≤a≤b≤100000≤a≤b≤10000.Youmustreaduntiltheendofthefile.

 

　　Output

 

　　Foreachpaira,ba,bread,youmustoutputthepercentageofprimenumbersproducedbytheformulain

 

　　thisinterval(a≤n≤b)(a≤n≤b)roundedtotwodecimaldigits.

 

　　SampleInput

 

　　039

 

　　040

 

　　3940

 

　　SampleOutput

 

　　100.00

 

　　97.56

 

　　50.00

 

　　题意：

 

　　输入数据a和b，求a和b之间数经过n^{2}+n+41n2+n+41为素数的所占比值保留两位小数；

 

　　思路：

 

　　数据范围00到1000010000啊~~~,懂!!!!!!!!_(:зゝ∠)_而且卡精度卡到死10^{-6}10−6真***恶心~~~~(>—<)~~~~；

 

　　主要进行素数打表（这是关键）o(︶︿︶)o唉（在这上面错了N次）不说了，说多了都是泪φ(≧ω≦*)?；

 

　　看代码：

 

　　1#include<iostream>

 

　　2#include<cstdio>

 

　　3#include<cstring>

 

　　4usingnamespacestd;

 

　　5#definelllonglong

 

　　6constintN=100100;

 

　　7boolisprime[N];

 

　　8boolPrime(inta)//判定素数

 

　　9{

 

　　10for(inti=2;i*i<=a;i++)

 

　　11if(a%i==0)

 

　　12returnfalse;

 

　　13returntrue;

 

　　14}

 

　　15voidIsprime()//进行打表

 

　　16{

 

　　17for(inti=0;i<N;i++)

 

　　18{

 

　　19if(Prime(i*i+i+41))

 

　　20isprime[i]=true;

 

　　21else

 

　　22isprime[i]=false;

 

　　23}

 

　　24}

 

　　25intmain()

 

　　26{

 

　　27Isprime();

 

　　28inta,b;

 

　　29while(cin>>a>>b)

 

　　30{

 

　　31ints=0;

 

　　32for(inti=a;i<=b;i++)

 

　　33{

 

　　34if(isprime[i])

 

　　35s++;//记录个数；

 

　　36}

 

　　37doublez=(double)s/(double)(b-a+1)*100+0.00000001;//卡精度

 

　　38printf(“%.2lf\n”,z);

 

　　39}

 

　　40return0;

 

　　41}

 

　　ViewCode

 

　　实践是检验真理的唯一标准