Meertens数
Posted feedbacks - Other
r が、その桁の最大値を超えたときを狩れば結構削れますよ。
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 | void _searchMeertens(int keta, int count, unsigned long long int r, unsigned long long int n, unsigned long long int nmax)
{
int x;
n *= 10;
for (x = (count == 0); x < 10; x++) {
if (x) {
r *= primes[count];
if (r > nmax) /* 枝狩り2 */
return;
n++;
}
if (keta == 0) {
if(r > n) /* 枝狩り*/
return;
if (r == n)
printf("Found Meertens %d\n", n);
}else{
_searchMeertens(keta -1, count + 1, r, n, nmax);
}
}
}
void searchMeertens(int keta)
{
int x;
unsigned long long int nmax;
time_t t;
t = time(NULL);
for (x = 0; x < keta; x++) {
nmax = (unsigned long long)pow(10.0, x + 1) - 1UL;
_searchMeertens(x, 0, 1, 0, nmax);
printf("keta = %d time = %d\n", x + 1, time(NULL) - t);
t = time(NULL);
}
}
|
nobsun
#4710()
Rating4/4=1.00
お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．
このような数のことをMeertens数と言うそうです．
32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．
1 reply [ reply ]