PowerShell で素数判定と素因数分解をするワンライナー

PowerShell のパイプラインで何かしようと思い立って、素数判定と素因数分解をしてみました。何故そんな抽象的なことを思いつくんでしょうね私は。

こちらもどうぞ

• To "Another PowerShell Math Challenge" - タイダログ

パイプラインについて

PowerShell といえばパイプラインです。あるコマンドレットが出力したオブジェクトが、その次のコマンドレットに渡り、さらに次へ次へと渡りながら処理されていきます。一番最後が終わると結果を画面に表示します。ベルトコンベアの要領ですね。

処理したい順番にコマンドレットを繋げるという点が書きやすさのポイントだと思います。Excel で関数を入れ子にするときは、先に処理する関数を中に、後に処理する関数を外に書きますよね。

=INT(MAX(1.1,2.2,3.3))

PowerShell なら処理したい順番に書けます。

@(1.1, 2.2, 3.3) | Measure-Object -Maximum | ForEach-Object {[int]$_.Maximum}

PowerShell を布教するときはこの点を推しましょう。間違っても「コンソール画面が青いです」などと言ってはいけません。PowerShell Core 6.0 からは黒いので。

動作環境

• Windows 10 20H2 (Build 19042.1165)
• Windows PowerShell 5.1.19041.1151
• PowerShell 7.1.3

素数判定

一番やりたかったのは素因数分解なんですが、その前に『素数』を数えて落ち着くんだ…

完成形

こちらを参考にしました。ありがとうございました。PowerShell はないので早速書きましょう。

qiita.com

0..29 | ? {$_ -gt 1} | ? {$_ -eq 2 -or $_ % 2 -ne 0} | ? {$target = $_; @(% {3..([Math]::Max(3, ([int]([Math]::Sqrt($_))))) | ? {$_ -lt $target} | ? {$_ % 2 -ne 0} | ? {$target % $_ -eq 0}}).Length -eq 0}

if も for も while も使わずにできました！

改行してインデントを付けて、エイリアスを使わずに書くとこうです。

0..29 | 
    Where-Object {$_ -gt 1} | 
    Where-Object {$_ -eq 2 -or $_ % 2 -ne 0} | 
    Where-Object {
        $target = $_; 
        @(
            ForEach-Object {
                3..([Math]::Max(3, ([int]([Math]::Sqrt($_))))) | 
                    Where-Object {$_ -lt $target} | 
                    Where-Object {$_ % 2 -ne 0} | 
                    Where-Object {$target % $_ -eq 0}
            }
        ).Length -eq 0
    }

ちなみに if や for を使って function にするとこうです。先述の投稿のC# のコードを PowerShell に書き換えました。

function IsPrime {
    param (
        [int]
        $Number
    ) 


    if ($Number -eq 2) {
        return $true
    } elseif ($Number % 2-eq 0 -or $Number -lt 2) {
        return $false
    } else {
        for ($i = 3; $i -le ([int]([Math]::Sqrt($Number))); $i += 2) {
            if ($Number % $i -eq 0) {
                return $false
            }
        }
    }
    return $true
}

判定方法

先述の投稿の内容をそのまま引用させていただきます。

1. 与えた整数が2であれば素数である。
2. 与えた整数を2で割り切れる(つまり偶数)、または与えた整数が2未満なら素数では無い。
3. 与えた整数を3以上の奇数で割る。割り切れれば素数では無い。割り切れなければ1個大きい奇数(つまり+2した値)で割り切れるか判定する。与えた整数の平方根以下の最大の奇数の全ての奇数で割り切れなかった場合、与えた整数は素数である。

平方根を使うと割り算の回数が少なくなるとか。ちゃんと勉強している人は効率的なことを考えられるんですね。

パイプラインでの実現方法

$true や $false で結果を示すのではなく、Where-Object や ForEach-Object を使って素数ではない整数を除外して、素数のみをパイプラインに流すという形にします。フィルターをかけるイメージです。

docs.microsoft.com

パイプラインを使うので、単一の整数を渡しても複数の整数を渡しても判定できます。

先ほどの判定方法を踏まえて、以下のようにします。

1. 2 と、3 以上の奇数のみをパイプラインに流す
2. 流れてきた整数を、「3 以上、その整数の平方根以下の奇数」で順に割り、どれでも割り切れなかったものをパイプラインに流す

1番目は簡単にできますね。0 から 29 で試しましょう。

# 2 と、3 以上の奇数のみをパイプラインに流す
0..29 | Where-Object {$_ -gt 1} | Where-Object {$_ -eq 2 -or $_ % 2 -ne 0}

# 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29

問題は2番目です。

流れてきた整数を、「3 以上、その整数の平方根以下の奇数」で順に割り、どれでも割り切れなかったものをパイプラインに流す

表にするとこういうことです。「割り切れる数」が - の整数（＝素数）のみをパイプラインに流します。

整数	平方根	割る数	割り切れる数
2	1.414	-	-
3	1.732	-	-
5	2.236	-	-
7	2.645	-	-
9	3	3	3
11	3.316	3	-
13	3.605	3	-
15	3.872	3	3, 5
17	4.123	3	-
19	4.358	3	-
21	4.582	3, 5	3
23	4.795	3, 5	-
25	5	3, 5	5
27	5.196	3, 5	3
29	5.385	3, 5	-

ややこしいので、まずは流れてきた整数を「3以上、その整数未満の奇数」で順に割るパターンを見ましょう。

整数を割り切れた奇数を配列に加えます。最終的に配列の要素数が 0 だった場合は、どの奇数でも割り切れなかった、つまり素数だと判断します。

# 3以上、その整数未満の奇数」で順に割る
0..29 | <略> | Where-Object {$target = $_; @(ForEach-Object {3..$_ | Where-Object {$_ -lt $target} | Where-Object {$_ % 2 -ne 0} | Where-Object {$target % $_ -eq 0}}).Length -eq 0}

# 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

平方根を利用すると次のようになります。3..([Math]::Max(3, ([int]([Math]::Sqrt($_))))) の部分です。

2 と 3 では平方根の整数部分が 1 なので 3..1 となり、1 で割ってしまいます。それではまずいので、[Math]::Max(3, 平方根) とすることで最小でも3になるようにしています。

# 平方根を利用
0..29 | <略> | Where-Object {$target = $_; @(ForEach-Object {3..([Math]::Max(3, ([int]([Math]::Sqrt($_))))) | Where-Object {$_ -lt $target} | Where-Object {$_ % 2 -ne 0} | Where-Object {$target % $_ -eq 0}}).Length -eq 0}

# 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

素因数分解

さて、一番やりたかった素因数分解です。これをする必要性は全くもってありません。主体的な探究活動です。

完成形

600 | % {$dividend = $_; 2..([int]([Math]::Sqrt($_))) | ? {$_ -gt 1} | ? {$_ -eq 2 -or $_ % 2 -ne 0} | ? {$target = $_; @(% {3..([Math]::Max(3, ([int]([Math]::Sqrt($_))))) | ? {$_ -lt $target} | ? {$_ % 2 -ne 0} | ? {$target % $_ -eq 0}}).Length -eq 0} | % {$divisible = $true; do {if ($dividend % $_ -eq 0) {$dividend /= $_; $_} else {$divisible = $false}} while ($divisible)}; if ($dividend -gt 1) {$dividend}}

改行してインデントを付けて、エイリアスを使わずに書くとこうです。インデントの付け方はこれでいいのだろうか。

600 | 
    ForEach-Object {
        $dividend = $_; 
        2..([int]([Math]::Sqrt($_))) | 
            # 素数判定↓
            Where-Object {$_ -gt 1} | 
            Where-Object {$_ -eq 2 -or $_ % 2 -ne 0} | 
            Where-Object {
                $target = $_; 
                @(
                    ForEach-Object {
                        3..([Math]::Max(3, ([int]([Math]::Sqrt($_))))) | 
                            Where-Object {$_ -lt $target} | 
                            Where-Object {$_ % 2 -ne 0} | 
                            Where-Object {$target % $_ -eq 0}
                    }
                ).Length -eq 0} |
                # 素数判定↑ 
                ForEach-Object {
                    $divisible = $true; 
                    do {
                        if ($dividend % $_ -eq 0) {
                            $dividend /= $_; 
                            $_
                        } else {
                            $divisible = $false
                        }
                    } while ($divisible)
                };
                if ($dividend -gt 1) {
                    $dividend
                }
    }

function 版です。上記の完成形を書き換えました。

function Invoke-PrimeFactorization {
    param (
        [int]
        $Number
    )
    

    $dividend = $Number
    [int[]]$factors = @()
    
    for ($i = 2; $i -le ([int]([Math]::Sqrt($Number))); $i++) {
        if (IsPrime -Number $i) {
            
            $divisible = $true

            do {
                if ($dividend % $i -eq 0) {
                    $dividend /= $i
                    $factors += $i
                } else {
                    $divisible = $false
                }
            } while ($divisible)
        
        }
    }

    if ($dividend -gt 1) {
        $factors += $dividend
    }

    return $factors
}

試し割り法

整数を素数で地道に割り続けます。試し割り法というそうです。

600 を素因数分解する場合、2 から 600の平方根 (= 24.494...) までの素数で割り続けたらいいそうです。平方根すごいな。

600 / 2 = 300 (600 = 2*300)
300 / 2 = 150 (600 = 2^2*150)
150 / 2 =  75 (600 = 2^3*75)
 75 / 3 =  25 (600 = 2^3*3*25)
 25 / 5 =   5 (600 = 2^3*3*5^2)

パイプラインでの実現方法

1. 2 から 600 の平方根までの整数をパイプラインに流す
2. そこから素数のみをパイプラインに流す
3. その素数で 600 を割り切れたら、その素数をパイプラインに流す

1番目は簡単ですね。下流で使うために 600 を変数に入れておきます。..演算子に [int] 以外を渡しても自動的に型変換してくれるそうですが、まあ一応。

# 2 から 600 の平方根までの整数をパイプラインに流す
600 | ForEach-Object {$dividend = $_; 2..([int]([Math]::Sqrt($_)))

# 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24

2番目。先述の素数判定のワンライナーを使います。

# そこから素数のみをパイプラインに流す
600 | ForEach-Object {$dividend = $_; 2..([int]([Math]::Sqrt($_))) | <素数判定>

# 2, 3, 5, 7, 11, 13, 17, 19, 23

3番目。while を使うことで、割り切れている間はその素数で割り続けます。割り切れずに最後まで残った整数も忘れずに流します。

# その素数で 600 を割り切れたら、その素数をパイプラインに流す
600 | <素数> | ForEach-Object {$divisible = $true; do {if ($dividend % $_ -eq 0) {$dividend /= $_; $_} else {$divisible = $false}} while ($divisible)}; if ($dividend -gt 1) {$dividend}}

# 2, 2, 2, 3, 5, 5

実行時間

600 を素因数分解するのに 0.027秒かかりました。ちなみに function 版は 0.006秒でした。

Measure-Command {600 | ForEach-Object {$dividend = $_; 2..([int]([Math]::Sqrt($_))) | Where-Object {$_ -gt 1} | Where-Object {$_ -eq 2 -or $_ % 2 -ne 0} | Where-Object {$target = $_; @(ForEach-Object {3..([Math]::Max(3, ([int]([Math]::Sqrt($_))))) | Where-Object {$_ -lt $target} | Where-Object {$_ % 2 -ne 0} | Where-Object {$target % $_ -eq 0}}).Length -eq 0} | ForEach-Object {$divisible = $true; do {if ($dividend % $_ -eq 0) {$dividend /= $_; $_} else {$divisible = $false}} while ($divisible)}; if ($dividend -gt 1) {$dividend}}}

Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 0
Milliseconds      : 27
Ticks             : 275540
TotalDays         : 3.18912037037037E-07
TotalHours        : 7.65388888888889E-06
TotalMinutes      : 0.000459233333333333
TotalSeconds      : 0.027554
TotalMilliseconds : 27.554

もう少し計ってみましょう。10のN乗 (3≦N≦9) と、それより小さい中で最大の素数を素因数分解します。

整数	実行時間 (s)
997	0.041
1,000	0.039
9,973	0.073
10,000	0.062
99,991	0.159
100,000	0.140
999,983	0.450
1,000,000	0.453
9,999,991	2.740
10,000,000	2.753
99,999,989	13.370
100,000,000	12.051
999,999,937	80.050
1,000,000,000	91.208

素数か否かでは実行時間は変わらないようですね。10のN乗なんて 2 と 5 で割り続けて終わりだろうと思うのですが、桁数が増えるにしたがって時間がかかります。何でだろう。何を勉強すればわかるのかな。

function 版だと 1,000,000,000 でも 1.185秒でした。

検算

# 素因数分解
$factors = 600 | ForEach-Object {$dividend = $_; 2..([int]([Math]::Sqrt($_))) | Where-Object {$_ -gt 1} | Where-Object {$_ -eq 2 -or $_ % 2 -ne 0} | Where-Object {$target = $_; @(ForEach-Object {3..([Math]::Max(3, ([int]([Math]::Sqrt($_))))) | Where-Object {$_ -lt $target} | Where-Object {$_ % 2 -ne 0} | Where-Object {$target % $_ -eq 0}}).Length -eq 0} | ForEach-Object {$divisible = $true; do {if ($dividend % $_ -eq 0) {$dividend /= $_; $_} else {$divisible = $false}} while ($divisible)}; if ($dividend -gt 1) {$dividend}}

# 素数を全て掛け合わせる
$factors | ForEach-Object -Begin {$product = 1} -Process {$product *= $_} -End {$product}

# 600

一連の流れを終えて

やりたいことをやりたいだけできて楽しかったです。

ただ明らかに構造化した function 版の方が分かりやすいですね。ワンライナーはきっとそのうち自分でもわからくなります。

な…何を書いているのかわからねーと思うが おれも 何を書いたのかわからなかった…

しかも function 版の方が遥かに速い。何でもかんでもワンライナーにすればいいってものでもないですね。

あと、セミコロンで文を繋いだものをワンライナーと呼んでいいのか、いまだによくわかりません。

参考

• 様々なプログラミング言語における素数判定 - Qiita

更新履歴

• 「パイプラインについて」の PowerShell のコードを、より Excel 関数の内容に近いものに変更 (2021/09/05)
• 全体的に、コード内でエイリアスを使わないように変更 (2021/09/05)
• 目次の下に「こちらもどうぞ」を追加 (2021/09/26)