fixedpoint.jp


年子平方数 (2009-01-15)

年子平方数の問題を教えてもらったので試しに C で解いてみました:

ts.c
#include <stdint.h>
#include <stdio.h>

#define NTH 21

int
main()
{
	int count = 0;
	uint64_t d10 = 10;
	uint64_t t = 1;
	uint64_t b = 1, s;
	uint64_t x;

#define FOUND(x, b) do {							\
		printf("%llu = %llu^2\n", x, b);			\
		if (++count >= NTH) return 0;				\
	} while (0)

	for (;;) {
		x = t*d10+t+1;
		while ( (s = b*b) < x) b++;
		if (s == x) FOUND(x, b);
		x += d10 - 1;
		while ( (s = b*b) < x) b++;
		if (s == x) FOUND(x, b);
		if (++t == d10 - 1) {
			t = d10;
			d10 *= 10;
		}
	}
	return 1;
}

実行例

$ gcc -Wall -W -o ts ts.c 
$ time ./ts 
8281 = 91^2
183184 = 428^2
328329 = 573^2
528529 = 727^2
715716 = 846^2
60996100 = 7810^2
82428241 = 9079^2
98029801 = 9901^2
1322413225 = 36365^2
4049540496 = 63636^2
106755106756 = 326734^2
453288453289 = 673267^2
538277538276 = 733674^2
998002998001 = 999001^2
20661152066116 = 4545454^2
29752082975209 = 5454547^2
2214532822145329 = 47058823^2
2802768328027684 = 52941178^2
7783702677837025 = 88225295^2
9998000299980001 = 99990001^2
110213248110213249 = 331983807^2

real0m20.580s
user0m11.094s
sys0m0.000s
$ 

この方法はまだまだ遅いようです。


© 2006-2023 fixedpoint.jp