4. 整数論に関係したアルゴリズム

ここでは素数を求めたり、約数を列挙したりといった整数論に関係するアルゴリズムを紹介する。

4.1. 素数を求める

4.1.1. エラトステネスのふるい

エラトステネスのふるいはあるNまでの素数を列挙するアルゴリズムである。

最初に2を素数として、その後の2の倍数を削除していく。次に残った3についても3の 倍数を削除していく。次に残っているのは5で同じようにする。これを繰り返すだけである。

エラトステネスのふるい

#include <iostream>
#include <vector>

std::vector<int> eratos(int N)//Nまでの素数を列挙
{
	std::vector<bool> a(N+1);
	for(int i=0; i<=N; i++) a[i] = true;
	a[0] = a[1] = false;
	
	for(int n=2; n*n<N; n++)
	{
		if(a[n]==true)
		{
			int j = n+n;
			while(j<=N)
			{
				a[j] = false;
				j += n;
			}
		}
	}
	std::vector<int> ret;
	for(int n=2; n<=N; n++)
	{
		if(a[n]==true) ret.push_back(n);
	}
	return ret;
}

int main()
{
	std::vector<int> ans = eratos(100);
	for(auto &x: ans) std::cout << x << " ";
	return 0;
}

4.2. 素因数分解

4.2.1. 試し割り法

非常にシンプルな方法である。 Nを素因数分解したいとき \(\sqrt N\) までの整数で割りきれるか試していく。割りきれた場合、その数で割りきれなくなるまでひたすら割りつづける。割れずに残った数も素因数であることに注意。

試し割り法

#include <iostream>
#include <vector>

std::vector<int> trial_division(int N)//Nを素因数分解する
{
	std::vector<int> ret;
	int n = N;
	for(int i=2; i*i<N; i++)
	{
		while(n%i == 0)
		{
			n/= i;
			ret.push_back(i);
		}
		if(n == 1) break;
	}
	if(n != 1) ret.push_back(n);
	return ret;
}

int main()
{
	std::vector<int> ans = trial_division(100);
	for(auto &x: ans) std::cout << x << " ";
	return 0;
}

4.3. 約数の列挙

4.3.1. 試し割り法

約数の列挙についても試し割りしていくことで可能である。Nの約数を列挙する場合、iが約数である場合、N/iも約数であることに注意。

#include <iostream>
#include <vector>

std::vector<int> enum_div(int n)//nの約数を列挙
{
	std::vector<int> ret;
	for(int i=1 ; i*i<=n ; ++i)
	{
		if(n%i == 0)
		{
			ret.push_back(i);
			if(i!=1 && i*i!=n)
			{
				ret.push_back(n/i);
			}
		}
	}
	return ret;
}

int main()
{
	std::vector<int> r = enum_div(10);
	for(auto i : r) std::cout << i << std::endl;
	return 0;
}