[Raku] 如何做質因數分解

作者:   發佈於:   #rakulang

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

Raku 語言中直接提供了 is-prime 函式給 Int 型別(整數),能去檢查所指定的整數是否為質數。

對於很大而未知是否為質數的數字,rakudo 內部以米勒-拉賓質數判定法為演算法去測試。

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

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

要列舉出所有質數,如此寫便行:

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

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

  1. n 不能被 p 整除,則忽略 p
  2. n 能被 p 整除,則:
  3. 找到一最大的整數 k,使 n 能被 n**k 整除
  4. nn / p**k

以 Raku 來實做上述步驟的話,則為:

my Int $n = @*ARGS[0].Int;
my Int $k = 1;
while $n %% $p {
    $n = $n div $p;
    $k++;
}
$k -= 1;

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

$n %% $p 這部份所用到的 %% 算符, 是用來判別「$n 是否為 $p 的整數倍」,也就是「$n 整除於 $p」的判別式。也可寫成 $n % $p == 0

若找到的 $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 raku

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

    for (2..*).grep(*.is-prime) -> $p {
        my $k = 1;
        while $n %% $p {
            $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 = @*ARGS[0].Int;
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