読者です 読者をやめる 読者になる 読者になる

素人がプログラミングを勉強していたブログ

プログラミング、セキュリティ、英語、Webなどのブログ since 2008

連絡先: すかいぷ:javascripter_  か javascripter あっと tsukkun.net skypeのほうがいいです

long long int

c

Problem 3 †
13195 の素因数は 5、7、13、29 である。

600851475143 の素因数のうち最大のものを求めよ。

http://odz.sakura.ne.jp/projecteuler/index.php?Problem%203

これを解こうとしたら600851475143ってintには収まらないしlongはどれくらいの大きさなのか、分からないなあと思って調べた。
下はsignedの場合。

  • char ±127
  • short int ±32767
  • int ±32767
  • long int ±+2147483647

あれ、longでも足りない…と思ったらC99にはlong long intという物があって

  • long long int ±9223372036854775807

これなら入る。で、それを使って書いてみた。

まず、nを素因数分解する時は2から√n以下まで割れば良いので(例えば9だったら√9=3まで割ればそれ以上の数が残っていることはないので)、まずsqrtが必要だと分かる。
ところがsqrtはdoubleしか受けつけずlong long intはキャストするとあふれてしまうので、自分で書く必要がある。

で、自分で書く場合どういう風なアルゴリズムを使えば良いか。
平方数は1, 4, 9, 16...で、1, 1+3, 1+3+5のように奇数を順に足していくことで計算できる。
これは、1x1の正方形のまわりに3,5…のL字型を足していって正方形を大きくするようなイメージで考えれば良い。
つまり、√8は4と9の間である、ということが、上の法則を使うと簡単に出せる。
この場合、isqrtはその数の平方根を越えない最大の数とすると便利なので、奇数を足していってnを越えたらカウンタ-1を返す、という風に実装すれば良い。

long long int isqrt(long long int n) {
	int i;
	for (i = 1; n > 0; i++) {
		n -= i * 2 + 1;
	}
	return i - 1;
}

ただし少し変形して奇数を足していくのではなく奇数を引いていくことにした。
で、これを使うとあとは簡単。

javascripter's
gist: 342466 — Gist

コメントにもある通り、実際には割ってくと最後にはnが1になるので、その時の数値をreturnすれば良い。isqrtはまあ、別の話題として。

#include <stdio.h>

long long int isqrt(long long int n) {
	int i;
	for (i = 1; n > 0; i++) {
		n -= i * 2 + 1;
	}
	return i - 1;
}

int main(void) {
	long long int n = 60085147, i, rt = isqrt(n), prime_factor = -1;
	for (i = 2; i <= rt; i++) {
		if (n % i == 0) {
			prime_factor = i;
			do {
				n /= i;
			} while (n % i == 0);
		}
	}
	printf("%lld\n", prime_factor);
	return 0;
}

long long intをprintfで表示する時はlldで表示すれば良い。