Project Euler——Problem 27 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 26
Project Euler——Problem 28

Project Euler——Problem 27

daybreakcx posted @ 2009年7月27日 17:29 in Prject Euler , 858 阅读

原题与答案:

Problem 27

27 September 2002

 

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40^(2) + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula  n² - 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, -79 and 1601, is -126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |-4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

 

Answer:-59231
 

分析与解答:

题目是求两个系数a和b,使得他们构成式子n^2+a*n+b,然后将n从0开始取值,直到不是素数为止,现在我们要在a和b的绝对值都在1000内的范围中找出能够令n取到最大的a和b,输出他们的乘积。本身这个题目不难,重点在于枚举和素数的判定,我们列一个素数表即可,考虑到题目中的提示,79的n已经是比较大的了,我们根据这个范围大概列了90000以内的素数表,然后穷举a和b,整个过程十分简单,我的源程序代码如下:

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. int ansa,ansb,ansn,a,b,n,i,j;
  4. bool nprime[90001];
  5. int calc(int a,int b)
  6. {
  7.         int i,s;
  8.         for (i=0;;i++)
  9.         {
  10.                 s=i*i+i*a+b;
  11.                 if (s<2||nprime[s]) break;
  12.         }
  13.         return i-1;
  14. }
  15. int main()
  16. {
  17.         memset(nprime,false,sizeof(nprime));
  18.         for (i=2;i<=300;i++)
  19.                 if (!nprime[i])
  20.                         for (j=i*i;j<=90000;j+=i)
  21.                                 nprime[j]=true;
  22.         ansn=-1;
  23.         for (a=-999;a<=999;a++)
  24.                 for (b=-999;b<=999;b++)
  25.                 {
  26.                         n=calc(a,b);
  27.                         if (n>ansn)
  28.                         {
  29.                                 ansa=a;
  30.                                 ansb=b;
  31.                                 ansn=n;
  32.                         }
  33.                 }
  34.         printf("%d\n",ansa*ansb);
  35.         return 0;
  36. }

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter