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 , 1283 阅读

原题与答案:

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. }

 

 

 

Clutte 说:
2018年10月22日 20:28

This project solution is very good for developers that can save them from time wasting in efficient way. Good news for students is that best essays for sale on online sites and buyers can easily get them without any problem.

move in move out cle 说:
2020年2月22日 21:36

These are more versatile over a vacuum better. Steam foliage no harmful residues in surfaces along with won’t discolor clothing. Using Classy Natural Cleaning Assistance, it’s entire steam ahead of time: whether inside Baby place, Bathroom, Home, on Flooring surfaces, Carpets along with Mattress. If your home is cleaned using steam, you could be sure that your particular baby keeps growing up throughout safe natural environment.


登录 *


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