Problem Description

Euler is a well-known matematician, and, among many other things, he discovered that the formula
n^{2} + n + 41n2+n+41 produces a prime for 0 ≤ n &lt; 400≤n<40. For n = 40n=40, the formula produces 16811681, which is 41 ∗ 4141∗41.Even though this formula doesn’t always produce a prime, it still produces a lot of primes. It’s known that for n ≤ 10000000n≤10000000, there are 47,547,5% of primes produced by the formula! So, you’ll write a program that will output how many primes does the formula output for a certain interval.

Input

Each line of input will be given two positive integer aa and bb such that 0 ≤ a ≤ b ≤ 100000≤a≤b≤10000. You must read until the end of the file.

Output

For each pair a, ba,b read, you must output the percentage of prime numbers produced by the formula in
this interval (a ≤ n ≤ b)(a≤n≤b) rounded to two decimal digits.

Sample Input

0 39
0 40
39 40

Sample Output

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>
 4 using namespace std;
 5 #define ll long long
 6 const int N=100100;
 7 bool isprime[N];
 8 bool Prime(int a)//判定素數
 9 {
10     for(int i=2; i*i<=a; i++)
11         if(a%i==0)
12             return false;
13     return true;
14 }
15 void Isprime()//進行打表
16 {
17     for(int i=0; i<N; i++)
18     {
19         if(Prime(i*i+i+41))
20             isprime[i]=true;
21         else
22             isprime[i]=false;
23     }
24 }
25 int main()
26 {
27     Isprime();
28     int a,b;
29     while(cin>>a>>b)
30     {
31         int s=0;
32         for(int i=a; i<=b; i++)
33         {
34             if(isprime[i])
35                 s++;//記錄個數；
36         }
37         double z=(double)s/(double)(b-a+1)*100+0.00000001;//卡精度
38         printf("%.2lf\n",z);
39     }
40     return 0;
41 }

實踐是檢驗真理的唯一標準