数論・素数に関するメソッドを実装する

数論・素数に関するメソッドを C# で一通り実装してまとめました。
通常の数値計算プログラミング用にも、また競技プログラミング用のライブラリとしても使えます。

機能は次の通りです。

Euclid 互除法

  • 最大公約数 (GCD)
  • 最小公倍数 (LCM)
  • ax + by = 1 の解 (Euclid 互除法の拡張)

素数

下の O(x) は計算量のオーダーを表します。

  • 素因数分解
    • O(√n)
  • 約数の列挙
    • O(√n)
  • 素数判定
    • O(√n)
  • n 以下の素数の列挙
    • およそ O(n)
  • m 以上 M 以下の素数の列挙
    • およそ O(√M + (M – m))

ソースコードは以下の通りです。
ここではシンプルな実装とし、例外処理も全体的に省略しています。
さらに無駄な演算処理を除くように改良することで、もう少し速くすることはできるはずです。

using System;
namespace AlgorithmLib.Numerics
{
public static class Euclidean
{
public static int Gcd(int a, int b) { for (int r; (r = a % b) > 0; a = b, b = r) ; return b; }
public static int Lcm(int a, int b) => a / Gcd(a, b) * b;
public static long Gcd(long a, long b) { for (long r; (r = a % b) > 0; a = b, b = r) ; return b; }
public static long Lcm(long a, long b) => a / Gcd(a, b) * b;
// ax + by = 1 の解
// 前提: a と b は互いに素。
// ax + by = GCD(a, b) の解を求める場合、予め GCD(a, b) で割ってからこの関数を利用します。
public static (long x, long y) ExtendedEuclid(long a, long b)
{
if (b == 0) throw new ArgumentOutOfRangeException(nameof(b));
if (b == 1) return (1, 1 - a);
var q = Math.DivRem(a, b, out var r);
var (x, y) = ExtendedEuclid(b, r);
return (y, x - q * y);
}
}
}
view raw Euclidean.cs hosted with ❤ by GitHub
using System;
using System.Collections.Generic;
namespace AlgorithmLib.Numerics
{
public static class Primes
{
/// <summary>
/// 指定された自然数を素因数分解します。O(√n)
/// </summary>
/// <param name="n">自然数。</param>
/// <returns>素因数のコレクション。n = 1 の場合は空の配列。</returns>
public static long[] Factorize(long n)
{
var r = new List<long>();
for (long x = 2; x * x <= n && n > 1; ++x)
while (n % x == 0)
{
r.Add(x);
n /= x;
}
// √n を超える素因数はたかだか 1 個であり、その次数は 1。
if (n > 1) r.Add(n);
return r.ToArray();
}
/// <summary>
/// 指定された自然数の約数をすべて求めます。O(√n)
/// </summary>
/// <param name="n">自然数。</param>
/// <returns>約数のコレクション。</returns>
public static long[] Divisors(long n)
{
var r = new List<long>();
for (long x = 1; x * x <= n; ++x)
if (n % x == 0) r.Add(x);
for (int i = r.Count - 1; i >= 0; --i)
{
var v = n / r[i];
if (v > r[i]) r.Add(v);
}
return r.ToArray();
}
/// <summary>
/// 指定された自然数が素数かどうかを判定します。O(√n)
/// </summary>
/// <param name="n">自然数。</param>
/// <returns>素数である場合に限り true。</returns>
public static bool IsPrime(long n)
{
for (long x = 2; x * x <= n; ++x)
if (n % x == 0) return false;
return n > 1;
}
/// <summary>
/// 指定された自然数以下の素数をすべて求めます。およそ O(n)
/// </summary>
/// <param name="n">自然数。</param>
/// <returns>素数のコレクション。</returns>
public static long[] GetPrimes(long n)
{
var b = new bool[n + 1];
for (long p = 2; p * p <= n; ++p)
if (!b[p])
for (long x = p * p; x <= n; x += p)
b[x] = true;
var r = new List<long>();
for (long x = 2; x <= n; ++x) if (!b[x]) r.Add(x);
return r.ToArray();
}
/// <summary>
/// 指定された範囲内の素数をすべて求めます。およそ O(√M + (M - m))
/// </summary>
/// <param name="m">最小値。</param>
/// <param name="M">最大値。</param>
/// <returns>素数のコレクション。</returns>
public static long[] GetPrimes(long m, long M)
{
var rM = (int)Math.Ceiling(Math.Sqrt(M));
var b1 = new bool[rM + 1];
var b2 = new bool[M - m + 1];
if (m == 1) b2[0] = true;
for (long p = 2; p <= rM; ++p)
if (!b1[p])
{
for (var x = p * p; x <= rM; x += p) b1[x] = true;
for (var x = Math.Max(p, (m + p - 1) / p) * p; x <= M; x += p) b2[x - m] = true;
}
var r = new List<long>();
for (int x = 0; x < b2.Length; ++x) if (!b2[x]) r.Add(m + x);
return r.ToArray();
}
}
}
view raw Primes.cs hosted with ❤ by GitHub

使用例を次に示します。

using System;
using AlgorithmLib.Numerics;
namespace AlgorithmConsole
{
class Program
{
static void Main(string[] args)
{
// 素因数分解
Console.WriteLine(string.Join(" * ", Primes.Factorize(2020)));
// 2 * 2 * 5 * 101
// 約数の列挙
Console.WriteLine(string.Join(" ", Primes.Divisors(2020)));
// 1 2 4 5 10 20 101 202 404 505 1010 2020
// 素数判定
Console.WriteLine(Primes.IsPrime(1000000007));
// True
// n 以下の素数の列挙
Console.WriteLine(string.Join(" ", Primes.GetPrimes(100)));
// 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
// m 以上 M 以下の素数の列挙
Console.WriteLine(string.Join(" ", Primes.GetPrimes(1000000000, 1000000100)));
// 1000000007 1000000009 1000000021 1000000033 1000000087 1000000093 1000000097
}
}
}
view raw Program.cs hosted with ❤ by GitHub

前回: 二分探索のライブラリ化

作成したサンプル

バージョン情報

  • C# 7.0
  • .NET Standard 2.0

参照

カテゴリー: アルゴリズム, 数学. タグ: . 2 Comments »

2件のフィードバック to “数論・素数に関するメソッドを実装する”

  1. 二分探索のライブラリ化 | Do Design Space Says:

    […] 前回: 競技プログラミングでも C# で簡潔に書きたい 次回: 数論・素数に関するメソッドを実装する […]

  2. LINQ で素数を求める (C#) | Do Design Space Says:

    […] LINQ を使わずに、より高速に素数を求める実装について 数論・素数に関するメソッドを実装する […]


コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。