n^2 + k (k=1,3,7,9,13,27) は、式全体として奇数にならないと素数である可能性はありません。
足し算の偶奇の組み合わせは、以下の 3 つがあります。
交換法則が使えますので、重複分は割愛します。
偶数 + 偶数 = 偶数 ... k は奇数なのでありえません
偶数 + 奇数 = 奇数 ... OK
奇数 + 奇数 = 偶数 ... NG
よって、k として奇数を加えるので n^2 の部分は偶数でなければいけません。
n ^ 2 の部分は、n * n と同じです。掛け算の偶奇の組み合わせは以下の 3 つがあります。
こちらも同様に交換法則が使えますので、重複分は割愛します。
偶数 * 偶数 = 偶数 ... OK
偶数 * 奇数 = 偶数 ... 同じ数 n を自乗するためありえません
奇数 * 奇数 = 奇数 ... NG
すなわち n は必ず偶数でなければいけません。
ですのでプログラムの素数走査のメイン部分は、2 から 2 ずつ n を増やして素数を走査するように修正します。
ループ内での偶数チェックは不要となります。
long ans = 0L; for (int n = 2; n < limit; n += 2) { long nn = (long)n * (long)n; if (is_consecutive_primes(prime_array, prime_cnt, nn)) { if (!is_prime(prime_array, prime_cnt, nn + 5) && !is_prime(prime_array, prime_cnt, nn + 11) && !is_prime(prime_array, prime_cnt, nn + 15) && !is_prime(prime_array, prime_cnt, nn + 17) && !is_prime(prime_array, prime_cnt, nn + 19) && !is_prime(prime_array, prime_cnt, nn + 21) && !is_prime(prime_array, prime_cnt, nn + 23) && !is_prime(prime_array, prime_cnt, nn + 25)) { ans = ans + (long)n; } } }
なお、n は int の範囲に収まりますが、n * n は int の範囲に収まらないため long への変換(キャスト)が必要です。
long nn = (long)n * (long)n;
また、ans の足し込み部分についても
ans += (long)n;
と書くときちんと足せるか不安なので、
ans = ans + (long)n;
のように書きます。
「じゃあ、n も long にしとけばいいのに！」と思うかも知れません。
プログラムを高速で動作させるために、なるべく int に寄せたいのです。
その昔、64 ビットパソコンでは long long の計算は問題ないのに、 32 ビットパソコンだとめちゃくちゃ遅くなって苦労したことがあります。アーキテクチャ的に 8 バイト長はそのままハードウェアでは扱えないので、ソフトウェア側（コンパイラ）でエミュレーションするわけですね。いちおう動作するようにはなるものの、どうしても速度が出なくなるわけです。
逆に小さすぎれば良いのかというとそれも違うのです。現在の CPU のアーキテクチャでは、4 バイト長を扱うのが一番得意で、4 バイト区切りでメモリをアクセスするのが最も効率が良いのです。C 言語においては、int が扱うバイト長が最適とされています*1。
ですので primes では bool 型の配列を使用していましたが、動作速度がおもわしくない場合は、あえて int にする事を検討するのも有りだと思います。
また、
「計算順序等を言語仕様を正確に理解していないとわからない・・・」
のような書き方はしてはいけない、と新入社員の頃に研修で習った記憶(遠い目)があるので、
危険なコードは仕事はもちろん趣味でも極力避けるのがポリシーです。
ただし、処理時間は変わりませんでしたｗ
元のプログラムでもループ内で偶数判定して重い処理をスキップしていたためと思われます。
処理時間は変わらないという結果になりましたが、プログラムのロジックとしてはこちらの方が正しいです。
*1:もうすぐ 8 バイト長の時代が来るかも知れません。
