Perl6: 質因數分解

作者：gugod 發佈於：2019/08/05 #perl6

質因數分解，就是要列出所有為質數的因數。一個直觀的暴力解法，就是列舉出所有質數，然後一個一個試試除看看。

Perl6 語言中直接提供了 is-prime 函式給 Int 型別（整數），能去檢查所指定的整數是否為質數。對於很大而未知是否為質數的數字，rakudo 內部以米勒-拉賓質數判定法為測試演算法。

首先是取得輸入，為了方便起見，直接拿第零個命令列參數作為 $n：

my $n = Int( @*ARGS[0] );

此處的 Int() 函式是將字串轉為 Int 型別的作用。

要列舉出所有質數，如此寫便行：

(2..*).grep(*.is-prime)

一般以徒手計算質因數分解時，大致上的步驟為是去對於所有質數 p 進行以以下測試:

若 n 不能被 p 整除，則忽略 p
若 n 能被 p 整除，則：
找到一最大的整數 k，使 n 能被 n**k 整除
令 n 為 n / p**k

以 Perl6 來實做上述步驟的話，則為：

# Int $n
my $k = 1;
while ($n % $p == 0) {
    $n = $n div $p;
    $k++;
}
$k -= 1;

這裡我刻意使用了 Int 型別專用的 div 算符 -- 既然已知 $n 能被 $p 整除，那麼，使用整數除法就可以讓 $n 保持在 Int 型別。相對來說，使用了 / 算符的 $n / $p 算式，其結果則必為 Rat 型別。

若找到的 $k 值大於 0，則表示 $p 為 $n 的因數之一，$p 與 $k 得被保存起來。

if $k > 0 {
    push @factors, $p => $k;
}

此處 @factor 內的元素型別為 Pair 。於其他語言中或被稱為 "Tuple"。

此處理過程的終止條件，就是在 $n 已經沒有因數之時。其一是在 $n 變為 1 的時候：

if $n == 1 {
    last;
}

另外一種狀況則是在 $n 本身已經變成質數之時。此時 $n 本身亦為的答案的一部份。

if $n.is-prime {
    push @factors, $n => 1;
    last;
}

算完之後則是把 @factors 印出來：

say @factors.map({ .key ~ "**" ~ .value  }).join(" * ");

將上述各片段整合起來後，以下是完整的程式：

#!/usr/bin/env perl6

sub prime-factorizatiion(Int $n is copy) {
    my @factors;

    for (2..*).grep(*.is-prime) -> $p {
        my $k = 1;
        while ($n % $p == 0) {
            $n = $n div $p;
            $k++;
        }
        $k -= 1;

        if $k > 0 {
            push @factors, $p => $k;
        }

        if ($n.is-prime) {
            push @factors, $n => 1;
            last;
        }
    }

    return @factors;
}

my $n = Int( @*ARGS[0] );
my @factors = prime-factorizatiion($n);

say @factors.map({ .key ~ "**" ~ .value  }).join(" * ");

主要做質因數分解的部份被包裝成一函式：

sub prime-factorizatiion(Int $n is copy) {
   ...
}

其中 $n 值宣告語法為 Int $n is copy，型別限為 Int，且為複本 (call by value)。

此篇文章中的程式 prime-factors 被我做成命令列程式，偶爾好用。使用效果如下：

# prime-factors 3884831087831
59**1 * 65844594709**1

附帶一提，其輸出與 zsh 的數值運算語法相合，因此可被放進 $(( ... )) 之中，再被 zsh 重新計算回原值。效果展示如下：

# echo $(($( prime-factors 3884831087831 )))
3884831087831