Meertens数
Posted feedbacks - C#
うっかり "{0}" を書き忘れたまま実行して、２時間を棒に振りました。やりなおしやりなおし。
32bit 符号無し整数４２億９４９６万７２９６個を、実に２時間１分１８秒で総当たり完了。８桁の数が１個だけヒットしました。
ちなみに 64bit 符号無しだと、およそ１００万年でしょうか。
……何かが根本的に間違っている気がします orz
それから、明らかに num.ToString() と Math.Pow が遅いよなぁ……と。
32bit 符号無し整数４２億９４９６万７２９６個を、実に２時間１分１８秒で総当たり完了。８桁の数が１個だけヒットしました。
ちなみに 64bit 符号無しだと、およそ１００万年でしょうか。
……何かが根本的に間違っている気がします orz
それから、明らかに num.ToString() と Math.Pow が遅いよなぁ……と。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | using System;
using System.Collections.Generic;
static class Program {
static void Main() {
DateTime before = DateTime.Now;
Console.WriteLine("meertens = {0}", string.Join(", ",
Array.ConvertAll<long, string>(Meertens(), delegate(long x) { return x.ToString(); })
));
Console.WriteLine("time = {0}", DateTime.Now - before);
}
static long[] Meertens() {
int[] primes = Primes(20);
List<long> meertens = new List<long>();
for(long num = uint.MaxValue; 0 <= num; num--)
if (Goedel(num, primes) == num)
meertens.Add(num);
return meertens.ToArray();
}
static double Goedel(long num, int[] primes) {
double goedel = 1;
string numstr = num.ToString();
for(int i = 0; i < numstr.Length; i++)
goedel *= Math.Pow(primes[i], numstr[i] - '0');
return goedel;
}
static int[] Primes(int count) {
List<int> primes = new List<int>();
primes.Add(2);
for(int num = 3; primes.Count < count; num += 2) {
foreach(int p in primes)
if (num % p == 0)
goto SKIP;
primes.Add(num);
SKIP:;
}
return primes.ToArray();
}
}
|
nobsun
#4710()
Rating4/4=1.00
お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．
このような数のことをMeertens数と言うそうです．
32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．
1 reply [ reply ]