問題
projecteuler.net
日本語訳→http://www.odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2049
4桁の素数を全部出します
一瞬です
等差数列の素数を選びます
3つの素数Pm, Pn, Poが公差dの関係になってるとのことなので、
素数Pmと素数Po (m < o)を選び、d = (Po - Pm) / 2から
Pn = Pm + d が存在するか調べます。
使ってる字は一緒か調べる
素数Pm, Pn, Poを文字列にしてソートします。
同じ数字を使ってるならソート結果は同一になるはずなので、あとはチェックするだけです。
コード
using System; using System.Linq; namespace ProjectEuler.Problem49 { class Program { static void Main(string[] args) { int[] primes = ES(1000, 10000); for (int i = 0; i < primes.Length; i++) { for (int sp = primes.Length - 1; sp >= i + 2; sp--) { int v = primes[i] + (primes[sp] - primes[i]) / 2; if (Array.BinarySearch(primes, v) >= 0) { if (CheckNumber(primes[i].ToString(), v.ToString(), primes[sp].ToString()) == true) { Console.WriteLine($"{primes[i]}{v}{primes[sp]}"); } } } } } /// <summary> /// 各項は置換可能な数字か調べる /// </summary> static bool CheckNumber(string p1, string p2, string p3) { char[] s1 = p1.OrderBy(x => x).ToArray(); char[] s2 = p2.OrderBy(x => x).ToArray(); char[] s3 = p3.OrderBy(x => x).ToArray(); for (int i = 0; i < s1.Length; i++) { if ((s1[i] != s2[i]) | (s2[i] != s3[i])) return false; } return true; } //エラトステネスの篩 static int[] ES(int min, int max) { int[] ps = new int[max + 1]; for (int i = 0; i < ps.Length; i++) { ps[i] = i; } ps[1] = 0; for (int i = 2; i < ps.Length; i++) { for (int j = i; j < ps.Length; j++) { if (ps[i] != 0) break; } for (int j = 2 * i; j < ps.Length; j += i) { ps[j] = 0; } } return ps.Where(x => x >= min).ToArray(); } } }