The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

600851475143 の素因数のうち最大のものを求めましょう.

出典；Problem 3 - Project Euler

ソースコードはこちら

まぁ、大したコードではないですけども．

考え方

ポイントとしてはlong longを使うということ．数値計算とかでよく使うのはdoubleとかばっかりなので初めてかもしれません．

あとは、600851475143まで真面目にループを繰り返すのか？ということ．ループ回数を極端に減らすためにfactors(素因数)の二乗回でストップしておきました．

2014-03-13

【Project Euler #002】フィボナッチ数列をそのまま解く（C++）

Project Eulerの２問目をやっていきます

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

項の値が4,000,000以下の, 偶数値の項の総和を求めよ

出典；Problem 2 - Project Euler

フィボナッチ数列ってなんだっけ？

昔、ミステリー小説によく出ていて、フィボナッチ数列を解くことが犯人への手がかりみたいなのが多かったですが、最近は使い古されたためか廃れてきましたね．

さてさて、フィボナッチ数って何？って話の途中でした．Wikipediaの解説を見たほうが早いかもしれませんが、簡単に言うとこんな数列です．

これの偶数値を足していくわけです．

\[{\begin{cases} ~~~F_0=0\\ ~~~F_1=1\\ ~~~F_{n+1}=F_n+F_{n+1} (n\ge 0)\end{cases} }\]

実際に書いてみる

例によってVisual studioのC++を使います．

基本的な指針としては

無限ループを回す
フィボナッチ数列を計算する
n項目の値が偶数かを判定する
400万を超えたらbreakする

ということです。ただし、毎回フィボナッチ数を呼び出して計算するのも非効率な気がしてきたので、こんなふうに書き換えました。

スマートなコードではない気がしますが、まぁパッと思いつくのはこんなもんかと。

2014-03-09

【Project Euler #001】ウィキペディアに反して解答してみる。（C++、Java）

２年位前にProject Eulerというのをやって記事にしました。前のブログの大清掃に伴い消してしまうのは勿体無いので、改定してこっちのブログに記載します。

プロジェクト・オイラーって何？って感じですが、簡単にいえばプログラミング問題集みたいなものです。下のリンクが公式ページですが、こちらのWikiにも詳しく書いています．

<a href="https://projecteuler.net/" data-mce-href="https://projecteuler.net/">About - Project Euler</a>

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ。

出典；Problem 1 - Project Euler

gist.github.com

JAVAだとこんな感じ

ウィキペディアでは、包含排除の定理を使って解くことを推奨していますが、まぁ、このくらいなら普通にループ計算したほうが速いかと。