Prime Time
Euler is a well-known matematician, and, among many other things, he discovered that the formula n2 +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
题意： 求给定的a,b 内的 i ,f(i)为非质数的个数占总数的百分比。f( n ) =n^2+n+41;
思路： 开始想的是
对于f( n )=n^2+n+41= n(n+1) + 41;
即对于每个数只需要考虑是否为 40 or 41 的倍数就行，写了一发果断被WA。
然后发现这样太草率，而且没有逻辑。
一看数据一点都不大，发现可以直接暴力过。
暴力打表 。
代码：
#include<cstdio> #include<cmath> #include<cstring> #define maxn 10010 using namespace std; int a[maxn]; void init() { memset(a,0,sizeof a); for(int i=1;i<maxn;i++) { int x=i*i+i+41; int flag=0; for(int j=2;j*j<=x;j++) { if(x%j==0) flag=1; } if(flag==1) a[i]=1; } for(int i=1;i<maxn;i++) a[i]+=a[i-1]; } int main() { init(); int n,m; while(scanf("%d%d",&n,&m)!=EOF) { double s=a[m]-a[n-1]; printf("%.2lf\n",(m-n+1-s)/(m-n+1)*100.0+1e-8); } return 0; }
