卒研メモ:GNU MPで素数日を調べる

 GMP(GNU MP)の機能として,整数が素数であるかどうかを確認する機能があります(数論関数のmpz_probab_prime_p関数)。詳細はマニュアルかソースプログラムを読んでいただくとして,本日(20170627)も素数日でした。

 ということで,本日が素数日かどうか,次の素数日(mpz_nextprime関数)がいつになるのかを教えてくれる機能をGMPサンプルプログラムに追加しました。

 ということで,この応用問題として「素数日でない時にはその数を素因数分解せよ」を出題しておきます。結構面倒なので,効率的な素因数分解方法を探求して下さい。

投稿者: T.Kouya

静岡理工科大学 情報学部 コンピュータシステム学科 教員