問題タブ [pari-gp]

PARI/GP には、a の最小の素因数を見つける関数、t_INTまたは整数の部分因数分解を実行する関数がありますか?

たとえば、番号がある場合：

2 つの巨大な素因数が含まれてfactor(a)いるため、実行に時間がかかります。しかし、が の約数であるaことを見つけるのは非常に簡単です。17a

もちろん、この場合forprime(p=2,,a % p == 0 && return(p))、因数を見つけるために、または同様の試行分割を使用することもできました。しかし、たとえば、最小の因数が 20 桁の 10 進数だった場合、それは非現実的であり、その場合の洗練された方法を使用したかったかもしれませんfactor。

factorしたがって、部分的な因数分解に満足している、または重要なのは最小の非自明な除数などであることを示す何らかのフラグを使用して呼び出すことができれば理想的です。

整数値を整数入力に返す関数があります。出力値は比較的まばらです。この関数は、入力値 1....2^16 に対して約 2^14 の一意の出力のみを返します。特定の出力を生成する入力をすばやく見つけることができるデータセットを作成したいと考えています。

現在、データセットをリストのマップに保存しており、各出力値が入力値のリストのキーとして機能しています。これは遅いようで、スタック スペース全体を使用しているように見えます。データセットを作成/保存/アクセスするより効率的な方法はありますか?

追加: 私の sparesearray() 関数にかかる時間は、入力値 (リストに格納された値) に対する出力値 (つまりキー) の比率によって大きく異なることがわかりました。以下は、多数のリストを必要とし、それぞれに少数の値しかない関数にかかった時間です。

それぞれが多くの値を持ついくつかのリストのみを必要とする関数にかかる時間は次のとおりです。

ご覧のとおり、時間は指数関数的に増加します。

これが私のコードです：