|
⇤ ← 2012-12-22 10:53:24時点のリビジョン1
サイズ: 1353
コメント:
|
← 2012-12-22 10:54:20時点のリビジョン2 ⇥
サイズ: 1341
コメント:
|
| 削除された箇所はこのように表示されます。 | 追加された箇所はこのように表示されます。 |
| 行 5: | 行 5: |
| f(n)が0以上d以下の整数について素数となるようaとbを定める（|a| < 1000, |b| < 1000）。このときdが最大となるaとbの積を求める。 | f(n)が0 <= n <= dについて素数となるようaとbを定める（|a| < 1000, |b| < 1000）。このときdが最大となるaとbの積を求める。 |
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 }
