原文: 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
回答4件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/08/22 14:18
2018/08/22 15:51
2018/08/22 15:55
2018/08/22 16:10 編集
2018/08/22 16:23 編集
2018/08/22 17:11
2018/08/22 17:16
2018/08/22 17:23
2018/08/22 21:04 編集
2018/08/22 17:31
退会済みユーザー
2018/08/22 22:45
2018/08/23 00:58 編集