Project Eulerの問題をC++で解く．
目次
問題
The prime factors of 13195 are 5, 7, 13 and 29.
https://projecteuler.net/problem=3
What is the largest prime factor of the number 600851475143 ?
英語わからない．和訳くれ
和訳
13195の素因数は，5, 7, 13, 29である．
600851475143 の素因数のうち最大の数値はいくらか？
解答
6857
プログラム
考え方
この問題は，素数判定と素因数分解を行う必要がある．
素数判定の関数と素因数分解の関数を作成し，素因数の最大値を求める．
ソースコード
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
namespace
{
bool IsPrime(const unsigned long &num)
{
if (num < 2)
{
return false;
}
if (num == 2)
{
return true;
}
if (num % 2 == 0)
{
return false;
}
auto sq = static_cast<unsigned long>(std::sqrt(num));
for (unsigned long i = 3; i <= sq; i += 2)
{
if (num % i == 0)
{
return false;
}
}
return true;
}
std::vector<unsigned long> PrimeFactrization(const unsigned long &num)
{
std::vector<unsigned long> list;
if (num < 2)
{
return list;
}
if (IsPrime(num))
{
list.emplace_back(num);
return list;
}
unsigned long istep = 0;
auto tmp = num;
while (true)
{
bool flag = true;
unsigned long nfac = 0;
if (istep == 0)
{
nfac = 2;
}
else
{
nfac = 2 * istep + 1;
}
if (IsPrime(nfac))
{
if (tmp % nfac == 0)
{
tmp /= nfac;
list.push_back(nfac);
flag = false;
}
}
if (tmp == 1)
{
break;
}
if (flag)
{
istep++;
}
}
return list;
}
} // namespace
int main()
{
auto factors = PrimeFactrization(600851475143);
std::cout << "Answer is " << *(std::max_element(factors.begin(), factors.end())) << std::endl;
return 0;
}ソースコード（アルゴリズム）説明
素数判定関数
bool IsPrime(const unsigned long &num)素数判定アルゴリズムは，逐次判定方法や確率的素数判定などがあるが，今回はより簡単な逐次判定方法を用いている．
高速化（効率化）のため，逐次判定の判定範囲を平方根以下（static_cast(std::sqrt(num))）としている．
auto sq = static_cast<unsigned long>(std::sqrt(num));
for (unsigned long i = 3; i <= sq; i += 2)
{
if (num % i == 0)
{
return false;
}
}
return true;
確率的素数判定は，GitLabリポジトリ内ですでに実装済みですので，
興味があれば眺めてみてください
https://gitlab.com/penguin-lab/projecteuler
素因数分解の関数
std::vector<unsigned long> PrimeFactrization(const unsigned long &num)返り値は，素因数一覧をstd::vectorで得られる．
実行
$ g++ -O3 -o problem3 main.cpp
$ ./problem1Answer is 6857リポジトリ（GitLab）
Project Eulerの問題をまとめたものはこちらのリポジトリにあるので，確認してみてください(⌒∇⌒)
https://gitlab.com/penguin-lab/projecteuler
最後に
内容に誤りや不具合，ご意見があればコメントを残して頂けるとありがたいです
アルゴリズム勉強のおすすめ書籍
アルゴリズムは，プログラミング言語自体の勉強ではなく，問題を解決するための手順や方法のこと．
プログラミング言語の基礎を身に付けた後に学ぶものがアルゴリズムである．
効率的や高速なプログラムを書くことが出来るようになるだろう．
あわせて読みたい
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 | 渡部 有隆, Ozy（協力）, 秋葉 拓哉（協...
Amazonで渡部 有隆, Ozy（協力）, 秋葉 拓哉（協力）のプログラミングコンテスト攻略のためのアルゴリズムとデータ構造。アマゾンならポイント還元本が多数。一度購入いた...
あわせて読みたい
プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニ...
Amazonで秋葉 拓哉, 岩田 陽一, 北川 宜稔のプログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～。ア...
あわせて読みたい
アルゴリズムイントロダクション 第3版 総合版：世界標準MIT教科書 | Thomas H. Cormen, Clifford Stein, R...
AmazonでThomas H. Cormen, Clifford Stein, Ronald L. Rivest, Charles E. Leiserson, 浅野 哲夫, 岩野 和生, 梅尾 博司, 山下 雅史, 和田 幸一のアルゴリズムイントロダ...
コメント