質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

4回答

1838閲覧

PE27 「二次式素数」 正解が出せない

opyon

総合スコア1009

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

2クリップ

投稿2018/08/22 06:54

編集2018/08/22 17:09

原文: Quadratic primes Problem 27
日本語翻訳サイト: Problem 27 「二次式素数」

何か思い込みをしてるのか堂々巡りが続いていて正解が出せなくて困っています。
客観的におかしいところやヒントやアドバイスなどあればご指摘頂ければ幸いです。

※正解の出せるコード一式などは検索すれば見つかると思うので大丈夫です。
最初に自力で正解出せるまではなるべく正解のコードなどは見ないようにしてます。
正解の値のみ検索して答え合わせだけしています。

java

1/** 2 * https://projecteuler.net/problem=27 3 * Quadratic primes Problem 27 4 * 5 * Problem 27 「二次式素数」 6 * http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2027 7 * 8 * 正解:-59231 9 * 10 */ 11public class pe_10027 { 12 13 public static void main(String[] args) { 14 long start = System.currentTimeMillis(); 15 16 func(1000); 17 18 long end = System.currentTimeMillis(); 19 System.out.println((end - start) + "ms"); 20 } 21 22 static void func(int num) { 23 24 final int s = num * -1 + 1; 25 final int e = num; 26 27 int a = 0; 28 int b = 0; 29 int n = 0; 30 int ans = 0; 31 32 boolean isTest = true; 33 34 for (int i = s; i < e; i+=2) {//奇数のみ 35 for (int j = 1; j <= e; j+=2) {//奇数のみ 36 int k = 0; 37 while (true) { 38 if (isPrime(k * k + k * i + j)) { 39 if (n < k) { 40 n = k + 1;//修正:0の時もカウント 41 a = i; 42 b = j; 43 ans = i * j; 44 if (isTest) 45 printAnswer(a, b, n, ans); 46 } 47 } else { 48 break; 49 } 50 k++; 51 } 52 } 53 } 54 printAnswer(a, b, n, ans); 55 } 56 57 static void printAnswer(int a, int b, int n, int ans) { 58 System.out.println("a:" + a + " b:" + b + " n:" + n); 59 System.out.println(ans); 60 } 61 62 static boolean isPrime(int x) { 63 64 //追記:自己解決 65 //引数xが1以下でも処理していたのが原因でした。 66 //下記条件を追加するだけで正解が出ました。 67 if (x <= 1) { 68 return false; 69 } 70 //追記終わり。 71 72 //判定範囲は√xまでで良いので修正 73 //for (int i = 2; i <= x / 2; i++) { 74 for (int i = 2; i <= Math.sqrt(x) ; i++) { 75 if (x % i == 0) { 76 return false; 77 } 78 } 79 return true; 80 } 81}

出力結果
a:-999 b:61 n:1010
-60939
546ms


追記:正解出ました。
a:-61 b:971 n:70
-59231
286ms


追記2:素数判定範囲は√までで良いので修正
for (int i = 2; i <= Math.sqrt(x) ; i++) {
a:-61 b:971 n:70
-59231
58ms


追記3:n=0の時もカウントしてるので出力で+1するように修正

java

1//n = k;修正前 2n = k + 1;//修正後:0の時もカウント

追記4:a,bの探索範囲は奇数のみで良いので修正

java

1 for (int i = s; i < e; i+=2) {//奇数のみ 2 for (int j = 1; j <= e; j+=2) {//奇数のみ

a:-61 b:971 n:70
-59231
37ms

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答4

0

ベストアンサー

こんにちは、問題を見たところa,bの取りうる値、およびその範囲を求めることがループする回数を減らす
すなわち処理速度を上げる鍵だと思います。結論から言うと,aは奇数bは3以上の素数となります。
理由を以下自分なりにまとめました。
イメージ説明
~~
また、f(n) = n ^ 2 + an + bが f(n) = (n + i)(n + j)のように因数分解できる形だと素数にならないので2次方程式の解と係数の関係を使ってa,bの取りうる値をさらに絞り込みました。
(結果的にこれがなくても求められましたが、処理速度は上がると思います...)~~
ごれを踏まえ、以下のようなメソッドを用意しました。

  • 素数かどうか判定するメソッド
  • n ^ 2 + an + bを出力するメソッド

- f(n)が因数分解されるかどうか判定するメソッド

  • 求める長さを求めるメソッド (while文を使って合成数になった瞬間打ち切ればOK!!)

java

1 2public class Main { 3 4 public static void main(String[] args){ 5 6 int []max_data = new int[3]; 7 String []text = {"a","b","length"}; 8 9 for(int a = 999; a >= -999; a -= 2){ 10 for(int b = 999; b >= 3; b -= 2){ 11 if(is_length(a,b) > max_data[2]){ 12 max_data[2] = is_length(a,b); 13 max_data[0] = a; 14 max_data[1] = b; 15 } 16 } 17 } 18 for(int i = 0; i < 3; i++){ 19 System.out.print(text[i] + " = " + max_data[i] + " "); 20 } 21 int answer = max_data[0] * max_data[1]; 22 System.out.println("積は" + answer); 23 24 } 25 public static boolean is_prime(int n) 26 { 27 if(n <= 1){ 28 return false; 29 } 30 for(int i = 2; i <= (int)Math.sqrt(n); i++){ 31 if(n % i == 0){ 32 return false; 33 } 34 } 35 return true; 36 } 37 public static int func(int a, int b,int n) 38 { 39 return n * n + a * n + b; 40 } 41 42 public static int is_length(int a, int b){ 43 44 int length = 0; 45 int n = -1; 46 while(is_prime(func(a,b,++n))){ 47 length++; 48 } 49 return length; 50 } 51 52 53} 54

<実行結果>
a = -61 b = 971 length = 71 積は-59231

投稿2018/08/22 13:26

編集2018/08/22 22:40
退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2018/08/22 14:18

そういうことじゃないと思う 全探索でもとにかく正解を求めようとしてるのに合わないから質問してるんだと思う。 あなたの答えも違うみたいだし…。
opyon

2018/08/22 15:51

>全探索でもとにかく正解を求めようとしてるのに合わないから質問してるんだと思う。 そのとおりです。速度upなどはその後考えるようにしています。
opyon

2018/08/22 15:55

@Stars1024さん回答ありがとうございます。 解法のご提案や考察が凄いですね。数学が得意そうで羨ましいです。 コードそのまま実行してみましたが結果が違うようですが結果が同じなのでもしかすると同じ原因なのかもしれませんね。 一応自己解決したので質問の中で修正追記しています。
opyon

2018/08/22 16:10 編集

@Stars1024さんのコード見て、素数判定の範囲は判定対象の√までで良いことを以前教えていただいたのに忘れていました。修正したところ286msから58msまで速度upしました。 for (int i = 2; i <= Math.sqrt(x) ; i++) { その他ご提案の解法や考察なども取り入れられそうなものがあれば勉強のために実装してみます。
opyon

2018/08/22 17:11

@Stars1024さんご提案のa,bの範囲は奇数で良いところを実装してみました。(追記4)
opyon

2018/08/22 17:16

>bが素数である必要がある 実装してみましたが逆に処理速度が遅くなるので未実装としています。 恐らくn ^ 2 + an + bでも素数判定してるのでオーバーヘッドとなるのではないかと推察。
opyon

2018/08/22 17:23

>因数分解できる形だと素数にならない これも同じ理由(どちらにしても最後にn ^ 2 + an + bで素数判定するので) から実装していません。 それを判定する為の計算でオーバーヘッドになると推察します。
opyon

2018/08/22 21:04 編集

@Stars1024さんご提案の解法や考察から取り入れたものまとめです ありがとうございました。 >素数判定範囲は√まで =実装済 >aが奇数 =実装済 >bが奇数 =実装済 >bが素数 =未実装 ※→長くなったので別途回答のコード中で実装しました。 >因数分解 =未実装
opyon

2018/08/22 17:31

(コードは一部修正が必要ですが)ご提案頂いた解法や考察などはとても参考になりましたのでベストアンサーとさせていただきます。
退会済みユーザー

退会済みユーザー

2018/08/22 22:45

ご指摘ありがとうございます。素数かどうか判定するメソッドにn <= 1の場合を書くのを忘れていました。そのため、負の数も素数と判定されてしまったと思います。修正して正しいa,bが求まりました。 ただ、長さは70ではなく71だと思うのですが、違いますか? f(n) = n ^ 2 - 61n + 971において,nの値が0~70のときすべて素数でした。
opyon

2018/08/23 00:58 編集

>ただ、長さは70ではなく71だと思うのですが、違いますか? ありがとうございます。 71で合っているはずです。 回答コードを修正しました。
guest

0

確実におかしなところを1つ。
funcメソッド内のローカル変数isTestをいじっている箇所がないため、意味を成していない。

投稿2018/08/22 07:17

swordone

総合スコア20649

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

opyon

2018/08/22 07:24

ご指摘ありがとうございます。 処理途中でログを出すのにonoffして使っているつもりでしたが一般的では無いですか? if (isTest) printAnswer(a, b, n, ans);
opyon

2018/08/22 21:02

@swordoneさんのご指摘は下記のようなことでしょうか? ご指摘くださった意味がわかったような気がしたのですが合っていますか? 変更前 func(1000); 変更後 `func(1000, true);` `func(1000, false);`
guest

0

こんにちは、昨日書いた回答の方は修正済みで答えが求まりましたが、やはり処理速度が遅いので
別の視点から処理速度を上げる方法を考えました。
実際に処理速度が速くなってので,追記という形で回答したいと思います。

a,bの取りうる値は以前と同じです。

考えたこと

イメージ説明

これを踏まえたうえで、例えばあるa,bの値のよってlengthの暫定的な最大値が5だったとします。
するともし次のbの値が3の倍数の場合はlengthの最大値を塗り替えることは絶対に不可能なのでわざわざ計算しなくて
すみます。

先ほど説明した「bの2以上の最小の約数」を言い換えると「1以外でbを最初に割りきる自然数」となります。

これらを考慮してコードを実装しました。
if文を使って判定するのは
(i)「bの2以上の最小の約数」が暫定的な最大を超えるか
(ii) (i)をクリアした場合のみ,実際にlengthが暫定的な最大値を超えるか

(i),(ii)を使えば実際に計算する時間は短くなると思います。

例えば、a = -61, b = 971 , length = 71が暫定的な結果だったとき「bの2以上の最小の約数」が71未満のものはすべてカットされますのでその分,速くなると思います。

java

1public class Prime { 2 3 public static void main(String[] args){ 4 5 int []max = {0,0,0}; 6 String []text = {"a","b","length"}; 7 for(int a = 999; a >= -999; a -= 2){ 8 for(int b = 997; b >= 3; b -= 2){ 9 if(min_divisor(b) > max[2]){ 10 if(length(a,b) > max[2]){ 11 max[0] = a; 12 max[1] = b; 13 max[2] = length(a,b); 14 } 15 } 16 } 17 } 18 for(int i = 0; i < 3; i++){ 19 System.out.print(text[i] + ":" + max[i] + " "); 20 } 21 System.out.println("積:" + (max[0] * max[1])); 22 23 } 24 public static boolean is_prime(int n) 25 { 26 if(n <= 1){ 27 return false; 28 } 29 for(int i = 2; i <= (int)Math.sqrt(n); i++){ 30 if(n % i == 0){ 31 return false; 32 } 33 } 34 return true; 35 } 36 public static int min_divisor(int n) 37 { 38 if(!is_prime(n)){ 39 for(int i = 2; i <= (int)Math.sqrt(n); i++){ 40 if(n % i == 0){ 41 return i; 42 } 43 } 44 } 45 return n; 46 } 47 public static int func(int a, int b, int n) 48 { 49 return n * n + a * n + b; 50 } 51 public static int length(int a,int b) 52 { 53 int length = 0; 54 int n = 0; 55 while(is_prime(func(a,b,n))){ 56 length++; 57 n++; 58 } 59 return length; 60 } 61}

イメージ説明

投稿2018/08/23 13:18

退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

opyon

2018/08/23 19:20

追加の回答ありがとうございます。 前回と今回のコードにそのまま速度計測だけ付け加え実行したところ前回の方が速いようです。 前回のコード a = -61 b = 971 length = 71 積は-59231 32.548485ms 今回のコード a:-61 b:971 length:71 積:-59231 46.800983ms 速度計測方法 public static void main(String[] args){ long start = System.nanoTime(); (実際の処理) long end = System.nanoTime(); System.out.println((end - start) / 1000000f + "ms"); }
opyon

2018/08/23 19:41 編集

探索範囲を絞り込む計算過程が複雑になると逆に遅くなるような気がします。 詳しいことはまだ理解出来てないのですが計算量の求め方が参考になります。 https://qiita.com/asksaito/items/59e0d48408f1eab081b5 例えば私の今回の質問から回答までの実装をまとめると 質問初期 546ms 素数判定条件追加 1以下は処理しない 286ms 素数判定範囲修正 対象の√以下までで良い 58ms 素数判定範囲修正 a,bの探索範囲は奇数のみで良い 37ms bの探索範囲修正  bに代入する値を素数でリスト化 16ms 全件探索で実装し正解が出た後、実装は変えずに範囲だけ絞り込みました。 最後の素数をリスト化し実装するところは処理増加以上に効果があったので差し引き速くなったと思います。
opyon

2018/08/23 19:57

@Stars1024さんの今回のコードが遅くなっている原因の推測ですが、 while(is_prime(func(a,b,n))){ このメイン処理を通る前にも min_divisor でis_primeを通りさらにis_primeと同様な処理を通っています 合計3回ですね 絞り込みに必要な計算自体が絞り込む以上に時間が掛かっていると思われます。
opyon

2018/08/23 19:59

>するともし次のbの値が3の倍数の場合は 因みに私の最後に実装した事前に「bの素数リスト化」を代入の場合は既に3の倍数は除外されているのでこの判定は必要なくなります。
退会済みユーザー

退会済みユーザー

2018/08/27 07:38 編集

>前回と今回のコードにそのまま速度計測だけ付け加え実行したところ前回の方が速いようです。 えっ、そうですか? 私のcomputerだとこっちの方が速かったです。環境によって違うのですね。
opyon

2018/08/27 07:41

速度計測方法 public static void main(String[] args){ long start = System.nanoTime(); (実際の処理) long end = System.nanoTime(); System.out.println((end - start) / 1000000f + "ms"); }
退会済みユーザー

退会済みユーザー

2018/08/27 07:42

いや、 これ知っていますけれど
opyon

2018/08/27 07:51 編集

合計時間1秒だと正確に計測出来ていないのでは無いでしょうか?
退会済みユーザー

退会済みユーザー

2018/08/27 09:37 編集

最初作ったとき正常に動かなくて勘違いしていました。あとで作った方が少し 遅いですね。すみません。
opyon

2018/08/27 09:34

いえいえ。 この質問ではほとんど@Stars1024さんの提案や考察から実装して解決しました。 とても参考になりましたありがとうございました。
guest

0

自己解決済みでしたが参考までに載せておきます。
先に素数リストを生成してそれだけをループで回すと速くなりました。
(@Stars1024さんご提案の探索範囲bが素数の条件です。)

その他変更点
・速度計測をSystem.nanoTime();に変更
・テスト用ログ出力切り替えをfunc(1000, false);引数でonoff出来るように変更

追記:
出力結果n=素数の個数が1少なかったので修正
k++;インクリメントする位置が後だったのが原因

java

1 2import java.util.LinkedList; 3import java.util.List; 4 5/** 6 * https://projecteuler.net/problem=27 7 * Quadratic primes Problem 27 8 * 9 * Problem 27 「二次式素数」 10 * http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2027 11 * 12 * 正解:-59231 13 * 14 */ 15public class pe_10027 { 16 17 public static void main(String[] args) { 18 long start = System.nanoTime(); 19 20 func(1000, true); 21 22 long end = System.nanoTime(); 23 System.out.println((end - start) / 1000000f + "ms"); 24 } 25 26 static void func(int num, boolean test) { 27 28 final int s = num * -1 + 1; 29 final int e = num; 30 31 int a = 0; 32 int b = 0; 33 int n = 0; 34 35 //テスト用ログ出力 36 boolean isTest = false; 37 38 //素数リスト生成 39 int[] p = makePrimesArray(num); 40 41 for (int i = s; i < e; i += 2) {//奇数のみ 42 for (int j = 0; j < p.length; j++) {//素数のみ 43 44 int k = 0; 45 while (isPrime(k * k + k * i + p[j])) { 46 47 k++;//修正:0の時もカウントするように先に足す 48 49 if (n < k) { 50 n = k; 51 a = i; 52 b = p[j]; 53 54 //テスト用ログ出力 55 if (isTest) 56 printAnswer(a, b, n, a * b); 57 } 58 } 59 } 60 } 61 printAnswer(a, b, n, a * b); 62 } 63 64 static void printAnswer(int a, int b, int n, int ans) { 65 System.out.println("a:" + a + " b:" + b + " n:" + n); 66 System.out.println(ans); 67 } 68 69 /** 70 * 2からnまでの素数リストを生成 71 * @param n 72 * @return int[] 73 */ 74 static int[] makePrimesArray(int n) { 75 // int[] result = null; 76 LinkedList<Integer> arrPrimes = new LinkedList<Integer>(); 77 78 for (int i = 0; i < n; i++) { 79 if (isPrime(i)) { 80 arrPrimes.add(i); 81 } 82 } 83 int[] result; 84 85 return result = toArrayIntegerToInt(arrPrimes); 86 } 87 88 /** 89 * List<Integer> >>> int[] 90 * @param list : 91 * @return int[] 92 */ 93 static int[] toArrayIntegerToInt(List<Integer> list) { 94 int ls = list.size(); 95 int[] arr = new int[ls]; 96 for (int i = 2; i < ls; i++) 97 arr[i] = list.get(i); 98 return arr; 99 } 100 101 /** 102 * 素数(そすう、英: prime number)とは、 103 * 1 より大きい自然数で、 104 * 正の約数が 1 と自分自身のみであるもののことである。 105 * 試し割り: 2から√n以下の素数まで順番に割っていく方法。 106 * @param n 107 * @return boolean :素数ならtrueを返す 108 */ 109 static boolean isPrime(int n) { 110 if (n <= 1) { 111 return false; 112 } 113 if (n == 2) { 114 return true; 115 } 116 if (n % 2 == 0) { 117 return false; 118 } 119 for (int i = 3; i <= Math.sqrt(n); i += 2) { 120 if (n % i == 0) { 121 return false; 122 } 123 } 124 return true; 125 } 126} 127

出力結果
a:-61 b:971 n:70
-59231
15.597411ms

出力結果修正後
a:-61 b:971 n:71
-59231
15.954789ms

投稿2018/08/22 20:57

編集2018/08/23 01:03
opyon

総合スコア1009

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問