Project Euler Problem 3
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
先ほど実装したOptionalと、LINQ for C++を用いて、簡単に求めてみました。素因数クラスは、インクリメントするたびに次の素数をOptional付きで返します。このため、これ以上十数が出せない場合はOptionalから判定できます。それをgenerateしてmaxを求めますが、PrimeNumbersのインスタンスがgenerateで一度に作られるわけではなく、maxを求めるためにその都度計算されるところがポイントです。コンストラクタが呼び出されるのはOptionalの特性から仕方がないことというわけですね。
#include <stdio.h> #include <LINQ/cpplinq.hpp> #include "utils.h" using namespace utils; class PrimeNumbers { public: explicit PrimeNumbers(long long n) : n(n), q(n), value(1) { } PrimeNumbers(const PrimeNumbers& it) : n(it.n), q(it.q), value(it.value) { } PrimeNumbers& operator=(const PrimeNumbers& it) { n = it.n; q = it.q; value = it.value; return *this; } operator long long() const { return value; } Optional<PrimeNumbers> operator++() { for(++value; value <= q; ++value) { if(q % value == 0) { q /= value; return *this; } } return None<PrimeNumbers>(); } Optional<PrimeNumbers> operator++(int) { PrimeNumbers ret = *this; operator++(); return ret; } private: long long n; long long q; long long value; }; int main() { using namespace cpplinq; const Optional<PrimeNumbers> n = PrimeNumbers(600851475143); auto ret = generate( [&n]() { return ++(*n) ? to_opt(static_cast<long long>(*n)) : to_opt<long long>(); }) >> max(); printf("%lld", ret); getchar(); return 0; }
こんな感じでコールされます。
construct
copy
construct
@ generate
copy
construct
@ generate
copy
construct
@ generate
copy
construct
@ generate
copy
construct
@ generate
6857
このようにすると、例えば先頭5個の素数だけ欲しい場合は、
using namespace cpplinq; const Optional<PrimeNumbers> n = PrimeNumbers(6469693230); auto ret = generate( [&n]() { return ++(*n) ? to_opt(*n) : to_opt<PrimeNumbers>(); }) >> take(5) >> to_vector(); for(auto v : ret) { printf("%lld\n", static_cast<long long>(v)); }
と書けばいいので柔軟性が上がりますね。何らかの数列を作り上げて、それに対して何らかの処理をするということができるようになりました。
追記
operator++が、自信のクラス以外の方を返すのは気持ち悪いし、そもそもOptionalで自身のクラスではなくlong longがたを返せばいいので次のように変更しました。
#include <stdio.h> #include <LINQ/cpplinq.hpp> #include "utils.h" using namespace utils; class PrimeNumbers { public: explicit PrimeNumbers(long long n) : n(n), q(n), value(1) { printf("construct\n"); } PrimeNumbers(const PrimeNumbers& it) : n(it.n), q(it.q), value(it.value) { printf("copy\n"); } ~PrimeNumbers() { printf("destruct\n"); } PrimeNumbers& operator=(const PrimeNumbers& it) { n = it.n; q = it.q; value = it.value; return *this; } operator long long() const { return value; } Optional<long long> next() { for(++value; value <= q; ++value) { if(q % value == 0) { q /= value; return *this; } } return None<long long>(); } private: long long n; long long q; long long value; }; int main() { using namespace cpplinq; const Optional<PrimeNumbers> n = PrimeNumbers(600851475143); auto ret = generate( [&n]() { printf("@ generate\n"); const auto ret = n->next(); return ret ? to_opt(*ret) : to_opt<long long>(); }) >> max(); printf("%lld", ret); getchar(); return 0; }