FreeBASIC マニュアルのトップに戻る

FreeBASIC GMP ライブラリの素因数分解関数

目次→フォーラム→FreeBASIC→補足new header file GMP←オリジナル・フォーラム

GMP の素因数分解関数 左にメニュー・フレームが表示されていない場合は、ここをクリックして下さい

←リンク元に戻る プログラム開発関連に戻る

素因数分解結果  このページは、dodicat さんに new header file GMP で教えてもらった、任意精度算術ライブラリ GMP の素因数分解関数と、その使用例です。

参考:多倍長演算ライブラリ(GNU MP) Version 6.1.2マニュアル
https://na-inet.jp/na/gmp_ja/

環境準備:
ダウンロード GMP.7z でヘッダー・ファイルをダウンロードして、該当フォルダに保存します。
↑ FreeBASIC V 1.05.0 に最新ヘッダー・ファイルが含まれているので不要
gmp 6.1.0(gmp-6.1.0.7z) ファイルをダウンロードして、共有ライブラリ libgmp.a を該当フォルダに保存します。

素因数分解

 専用の関数を使うので高速です。
 21桁の数値 121,439,531,096,594,251,777 を、3分足らずで素因数分解します。
'by dodicat ≫ Dec 16, 2016 20:02 
'https://www.freebasic.net/forum/viewtopic.php?f=3&t=23225&start=30

#Include Once "gmp.bi"

Type Pfactors
   As String n
   As String f(Any)
   Declare Operator Cast() As String
End Type

Operator Pfactors.cast() As String   'printout
Print n,
If UBound(f)=1 Then Return "(prime)"
For z As Integer=1 To UBound(f)
   Print f(z);" ";
Next z
End Operator

'素因数分割して、結果を表示するとともに、結果を渡す関数
Function primefactors(number As String) As Pfactors
   
   Dim STARTT As Long
   Dim ENDTIME As Long
   Dim Minut As Integer
   
   STARTT=Val(Left(Time,2))*3600+Val(Mid(Time,4,2))*60+Val(Right(Time,2))
   
   Print number,
   Dim As Long i
   Dim As ZString * 10000 outtext
   Dim As __mpz_struct zero,one,two,three,six,Zmod,divisor,Zdiv,tmp,root,num
   mpz_init(@one)
   mpz_init(@tmp)
   mpz_init(@six)
   mpz_init(@Zdiv)
   mpz_init(@Zmod)
   mpz_init(@zero)
   mpz_init(@two)
   mpz_init(@three)
   mpz_init(@divisor)
   mpz_init(@root)
   mpz_init(@num)
   mpz_set_str(@num, number, 10)
   mpz_set_str(@zero,"0", 10)
   mpz_set_str(@two,"2", 10)
   mpz_set_str(@three,"3", 10)
   mpz_set_str(@six,"6", 10)
   mpz_set_str(@one,"1", 10)
   Dim As Pfactors p:p.n=number
   #Macro fill(x)
   i+=1
   ReDim Preserve p.f(1 To i)
   gmp_sprintf( @outtext,"%Zi", @x )
   p.f(i)=Trim(outtext)
   Print p.f(i);" ";
   #EndMacro
   #Macro Eliminate(x)
   mpz_mod(@Zmod,@num,@x)
   
   While Mpz_cmp(@Zmod, @zero) = 0 'number mod x=0
      mpz_div(@Zdiv, @num, @x) 
      mpz_init_set(@num, @Zdiv)
      fill(x)
      mpz_sqrt( @root,@num)
      mpz_add(@root,@root,@one) 'sqr(num)+1
      mpz_mod(@Zmod,@num,@x)
   Wend
   
   #EndMacro
   
   mpz_sqrt( @root,@num)
   mpz_add(@root,@root,@one)
   Eliminate(two)
   Eliminate(three)
   While  Mpz_cmp(@divisor,@root)<0'divisor<root
      mpz_add(@divisor,@divisor,@six)'divisor+=6 
      mpz_sub(@tmp,@divisor,@one)
      Eliminate (tmp)'((divisor-1))
      mpz_add(@tmp,@divisor,@one)
      Eliminate(tmp)'((divisor+1))
   Wend
   
   ' If number>1 Then 
   If  Mpz_cmp(@num,@one)>0 Then
      fill(num)
   End If
   'clean up
   mpz_clear(@one): mpz_clear(@tmp): mpz_clear(@six): mpz_clear(@Zdiv): mpz_clear(@Zmod)
   mpz_clear(@zero): mpz_clear(@two): mpz_clear(@three): mpz_clear(@divisor): mpz_clear(@root): mpz_clear(@num)
   If UBound(p.f)=1 Then Print " (素数)";
   Print

   ENDTIME = Val(Left(Time,2))*3600+Val(Mid(Time,4,2))*60+Val(Right(Time,2))
   Minut=(ENDTIME-STARTT)\60
   Print Using "処理時間は ### 分 ## 秒"; Minut; (ENDTIME-STARTT)-Minut*60
   Print
   
   Return p
End Function

'文字列置換
Function SAR(s0 As String,Find As String,Replacement As String) As String
   Dim s As String=s0
   Var position=InStr(s,Find)
   While position>0
      s=Mid(s,1,position-1) & Replacement & Mid(s,position+Len(Find))
      position=InStr(position+Len(Replacement),s,Find)
   Wend
   SAR=s
End Function

Dim As Pfactors x

Print "与えた整数",,"素因数"

x= primefactors(SAR("18,446,744,073,709,551,617",",","")) '数値のカンマを外す
x= primefactors(SAR("2,305,843,008,139,952,128",",",""))
x= primefactors("12345678909876543212345678909876822")
x= primefactors(SAR( "70,000,104,900,007",",",""))
x= primefactors(SAR( "1,111,111,111,111,111,111",",",""))
x= primefactors(Str(2*3*5*7*11*13*17*19ull))

x= primefactors(SAR( "121,439,531,096,594,251,777",",",""))
x= primefactors(SAR( "8,635,844,967,113,809",",",""))
Print

'変数 x は、素因数の最後の集合を含んでいます
'Print x

Print "何かキー入力で終了"
Sleep 

階乗を計算して、その値を素因数分解

 階乗の関数の引数として、乱数で範囲を設定して、自動で数値はめて階乗を計算します。
そして、その階乗の結果の数値を使って、こんどは素因数分解します。
'by dodicat ≫ Dec 17, 2016 0:12 
'https://www.freebasic.net/forum/viewtopic.php?f=3&t=23225&start=30

#Include Once "gmp.bi"

Dim Shared As ZString * 1000000 outtext
Dim Shared As Long Iprint '関数の中で表示するため

Type Pfactors
   As String n
   As String f(Any)
   Declare Operator Cast() As String
End Type

Operator Pfactors.cast() As String   '表示
   If UBound(f)=1 Then Return "(prime)"
   Dim As __mpz_struct tot,fz,n0
   mpz_init(@tot):mpz_init(@fz):mpz_init(@n0):mpz_set_str(@n0,n,10)
   mpz_set_str(@tot,"1", 10)
   Print n;" = ",
   For z As Integer=1 To UBound(f)
      mpz_set_str(@fz,f(z),10)
      mpz_mul(@tot,@tot,@fz)
     If z<UBound(f) Then Print f(z);"*"; Else Print f(z);
   Next z
   If Mpz_cmp(@tot,@n0) = 0 Then Print " --OK"
   mpz_clear(@tot): mpz_clear(@fz): mpz_clear(@n0)
End Operator

Function primefactors(number As String) As pfactors
   If Iprint Then Print number,
   Dim As Long i
   Dim As ZString * 10000 outtext
   Dim As __mpz_struct zero,one,two,three,six,Zmod,divisor,Zdiv,tmp,root,num
   Dim As __mpz_struct tot,fz,n0
   mpz_init(@tot):mpz_init(@fz):mpz_init(@n0):mpz_set_str(@n0,number,10)
   mpz_set_str(@tot,"1", 10)
   mpz_init(@one)
   mpz_init(@tmp)
   mpz_init(@six)
   mpz_init(@Zdiv)
   mpz_init(@Zmod)
   mpz_init(@zero)
   mpz_init(@two)
   mpz_init(@three)
   mpz_init(@divisor)
   mpz_init(@root)
   mpz_init(@num)
   mpz_set_str(@num, number, 10)
   mpz_set_str(@zero,"0", 10)
   mpz_set_str(@two,"2", 10)
   mpz_set_str(@three,"3", 10)
   mpz_set_str(@six,"6", 10)
   mpz_set_str(@one,"1", 10)
   Dim As pfactors p:p.n=number
   #Macro fill(x)
   i+=1
   ReDim Preserve p.f(1 To i)
   gmp_sprintf( @outtext,"%Zi", @x )
   p.f(i)=Trim(outtext)
   If Iprint Then
   Print p.f(i);" ";
   mpz_set_str(@fz,p.f(i),10)
   mpz_mul(@tot,@tot,@fz)
   End If
   #EndMacro
   #Macro Eliminate(x)
   mpz_mod(@Zmod,@num,@x)
   
   While Mpz_cmp(@Zmod, @zero) = 0 'number mod x=0
      mpz_div(@Zdiv, @num, @x) 
      mpz_init_set(@num, @Zdiv)
      fill(x)
      mpz_sqrt( @root,@num)
      mpz_add(@root,@root,@one) 'sqr(num)+1
      mpz_mod(@Zmod,@num,@x)
   Wend
   
   #EndMacro
   
   mpz_sqrt( @root,@num)
   mpz_add(@root,@root,@one)
   Eliminate(two)
   Eliminate(three)
   While  Mpz_cmp(@divisor,@root)<0'divisor<root
      mpz_add(@divisor,@divisor,@six)'divisor+=6 
      mpz_sub(@tmp,@divisor,@one)
      Eliminate (tmp)'((divisor-1))
      mpz_add(@tmp,@divisor,@one)
      Eliminate(tmp)'((divisor+1))
   Wend
   
   ' If number>1 Then 
   If  Mpz_cmp(@num,@one)>0 Then
      fill(num)
   End If
   
   If Iprint Then If Mpz_cmp(@tot,@n0) = 0 Then Print " --OK";
   '
   'clean up
   mpz_clear(@one): mpz_clear(@tmp): mpz_clear(@six): mpz_clear(@one): mpz_clear(@Zdiv): mpz_clear(@Zmod)
   mpz_clear(@zero): mpz_clear(@two): mpz_clear(@three): mpz_clear(@divisor): mpz_clear(@root): mpz_clear(@num)
   
   mpz_clear(@tot): mpz_clear(@fz): mpz_clear(@n0)
   If Iprint Then If UBound(p.f)=1 Then Print " (素数)";
   If Iprint Then Print
   Return p
End Function

'階乗
Function factorial(n As UInteger) As String '精度は自動設定
   Dim As __mpz_struct Intanswer
   mpz_init( @Intanswer)
   mpz_fac_ui(@Intanswer,n)
   gmp_sprintf( @outtext,"%Zi", @Intanswer )
   mpz_clear(@Intanswer)
   Return Trim(outtext)
End Function

#define range(f,l) Int(Rnd*((l+1)-(f))+(f))
Iprint=0
Randomize

'Do
'   Dim As pfactors x
'   Dim As ULong u=range(10,1000)
'   Dim As String f=factorial(u)
'   Print "number = ";"factorial(";u;")"
'   x=primefactors(f)
'   Print
'   Print "from cast()"
'   Print x
'   Print "______________________________"
'   Print "ESC(エスケープ)でループを抜ける。それ以外でループ継続。"
'   Sleep
'   Cls
'Loop Until InKey=Chr(27)

Print "35!= "; factorial(35)
Dim As pfactors x
x = primefactors("18446744073709551617")
Print x
Print "何かキー入力で終了"
Sleep 
 
補足 に戻る
←リンク元に戻る プログラム開発関連に戻る
ページ歴史:2016-12-18
日本語翻訳:WATANABE Makoto、原文著作者:dodicat , 2016-12-16 20:02

ホームページのトップに戻る

表示-非営利-継承