Login
Immutable PageDiscussionInfoAttachments
iz/競技プログラミング/Project Euler 027 Quadratic primes

MMA

http://projecteuler.net/problem=27

f(n) = n * n + a * n + b

f(n)が0 <= n <= dについて素数となるようaとbを定める(|a| < 1000, |b| < 1000)。このときdが最大となるaとbの積を求める。

   1 #include <iostream>
   2 #include <vector>
   3 #include <cstring>
   4 using namespace std;
   5 
   6 #define LIMIT (1000*1000)
   7 #define MAX 1000
   8 
   9 bool isPrime[LIMIT];
  10 vector<int> primes;
  11 
  12 void init() {
  13     memset(isPrime, 1, sizeof(isPrime));
  14     for (int i = 2; i < LIMIT; i++) {
  15         if (isPrime[i]) {
  16             if (i <= MAX) primes.push_back(i);
  17             for (int j = i+i; j < LIMIT; j+=i) {
  18                 isPrime[j] = false;
  19             }
  20         }
  21     }
  22 }
  23 
  24 int len(int a, int b) {
  25     int n;
  26     for (n = 0; ; n++) {
  27         if (!isPrime[n * n + a * n + b]) return n - 1;
  28     }
  29 }
  30 
  31 int main() {
  32     init();
  33     int max_len = 0;
  34     int ans = 0;
  35     // n = 0のとき式の値が素数となるので, bは素数
  36     for (int i = 0; i < primes.size(); i++) {
  37         int b = primes[i];
  38         for (int a = -999; a < 1000; a++) {
  39             int l = len(a, b);
  40             if (l > max_len) {
  41                 ans = a * b;
  42                 max_len = l;
  43             } 
  44         }
  45     }
  46     cout << max_len << endl;
  47     cout << ans << endl;
  48     return 0;
  49 }

iz/競技プログラミング/Project Euler 027 Quadratic primes (last edited 2012-12-22 10:54:20 by iz)