Prime Time
Euler is a well-known matematician, and, among many other things, he discovered that the formula n 2 + n + 41 produces a prime for 0 ≤ n < 40. For n = 40, the formula produces 1681, which is 41 ∗ 41. Even though this formula doesn’t always produce a prime, it still produces a lot of primes. It’s known that for n ≤ 10000000, there are 47,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 a and b such that 0 ≤ a ≤ b ≤ 10000. You must read until the end of the file.
Output
For each pair a, b read, you must output the percentage of prime numbers produced by the formula in this interval (a ≤ n ≤ b) rounded to two decimal digits.
Sample Input
0 39
0 40
39 40
Sample Output
100.00
97.56
50.00
别人都输是精度比较坑，但是我精度没出什么大问题
就是打表痛苦，打了两个，最开始以为要打到10的八次方，题目给的是3s时间限制，但是想想数组好像没开过那么大的，平方关系，开4次方就够了，又打了个素数表，不知道能不能减少点时间，也没测试。
这都不是事，最可恶的是输入没有换，是上道题的输入，最后莫名其妙的WA了好几次，这个脑子，啊
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define maxn 10010 #define inf 0x3f3f3f3f #define ll long long #define K 9.81 using namespace std; int dis[maxn], vis[maxn], cnt[maxn]; int main(){ int t, a, b, kcase = 1; memset(vis, 0, sizeof(vis)); for(int i = 2; i*i <= maxn; i++){ if(!vis[i]){ for(int j = i*i; j <= maxn; j += i){ vis[j] = 1; } } } int num = 0; for(int i = 2; i <= maxn; i++){ if(!vis[i]){ cnt[num++] = i; } } dis[0] = 0; dis[1] = 1; for(int i = 1; i < maxn; i++){ int c = i*i + i + 41; int flag = 0; for(int j = 0; cnt[j]*cnt[j] <= c; j++){ if(c % cnt[j] == 0){ flag = 1; break; } } if(flag){ dis[i+1] = dis[i]; } else{ dis[i+1] = dis[i]+1; } } while(~scanf("%d%d", &a, &b)){ int t = int(100000*(1.0*dis[b+1]-dis[a])/(b-a+1)); if(t%10 >= 5){ t /= 10; t++; } else{ t /= 10; } double sum = double(t); printf("%.2lf\n", sum/100); } return 0; }