38 再帰 Pythonで約数を求める

Python3で約数、最大公約数、最小公倍数を求めるプログラム。
再帰を使って自前で計算してみました。
ユークリッドの互除法、使ってません。

(Python2 整数の最大値でエラーになるかも)


目標
関数型を意識してループと代入を減らす。
約数をリストにする。


追加項目
最大公約数、最小公倍数
リストの全数字の掛け算
再帰の初期値も関数側で指定。
時間測定。


はまった点
再帰の回数が多すぎてエラー発生。

リストを渡す再帰呼出しの時
yakusu(arr.append(5))
みたいにするとエラーになる。
リストは呼び出し前に追加。


最初に約数をリストにする関数を作ります。
２つのリストから同じ数値を抜きだす関数。
さらに同じものと残ったものを取得する関数。
最後に配列の数を全部掛け合わせる関数。




次に再帰読み出しの初期値は固定値なので、
デフォルトで設定できるようにします。
（修正は約数をつくるものだけです）

Noneで指定してその時関数内で設定をしています。
（直指定だと複数回目に挙動がかわる時がある。
といった記事をみたので参考にしています。）


ここでたまたま、巨大な数の約数を求めた時、
再帰数の限度を越えるのかエラーが発生、
再帰の呼び出し数を減らす修正をします。




巨大な数字だと計算に時間がかかるので、
少し無駄を省いて、時間計測も追加、
9223372036854775807はpython3の限界値
限界値は演算結果が違います。


おまけで
巨大な数の最大公約数を求めてみました。
答え2は違うと思って、
2つの約数を求めると、あってそうです。

実行結果




コピペできる版です。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

import time print("***** yakusu *****") def yakusuSub(n,d,arr): if n==1:return arr if n/d==int(n/d): arr.append(d) return yakusuSub(n/d,d,arr) else: return yakusuSub(n,d+1,arr) def yakusu(n): return yakusuSub(n,2,[]) print(yakusu(81*165)) print(yakusu(2320)) print("***** kobai koyaku *****") def koyaku(a1,a2,arr): if len(a1)==0:return arr if a1[0] in a2: del a2[a2.index(a1[0])] arr.append(a1[0]) del a1[0] return koyaku(a1,a2,arr) def kobai(a1,a2,arr): if len(a1)==0: arr.extend(a2) return arr if a1[0] in a2: del a2[a2.index(a1[0])] arr.append(a1[0]) del a1[0] return kobai(a1,a2,arr) def multiply(arr,n): if len(arr)==0:return n n=n*arr[0] del arr[0] return multiply(arr,n) print( multiply(koyaku([2,3,3,5,7],[3,7,11],[]),1) ) print( multiply(kobai([2,3,3,5,7],[2,2,3,7,11],[]),1) ) print("***** yakusu2 *****") def yakusu2(n,d=None,arr=None): if d==None:d=2 if arr==None:arr=[] if n==1:return arr if n/d==int(n/d): arr.append(d) return yakusu2(n/d,d,arr) else: return yakusu2(n,d+1,arr) print(yakusu2(81*165)) print("***** yakusu3 *****") def yakusu3(n,d=None,arr=None): if d==None:d=2 if arr==None:arr=[] if n==1:return arr if n/d==int(n/d): arr.append(d) return yakusu3(n/d,d,arr) else: for d1 in range(int(d+1),int(n+1)): if n/d1==int(n/d1): return yakusu3(n,d1,arr) start = time.time() print(yakusu3(556505055652320)) print(yakusu3(9223372036854775807)) print(yakusu3(922337203685477580)) print( "time:"+str( round(time.time()-start,2) ) ) print("***** yakusu4 *****") def yakusu4(n,d=None,arr=None): if d==None:d=2 if arr==None:arr=[] if n==1:return arr if n/d==int(n/d): arr.append(d) return yakusu4(int(n/d),d,arr) else: for d1 in range(d+1,int(n+1/2)): if n/d1==int(n/d1): return yakusu4(n,d1,arr) else: return yakusu4(n,n,arr) start = time.time() print(yakusu4(556505055652320)) print(yakusu4(9223372036854775807)) print(yakusu4(922337203685477580)) print( "time:"+str( round(time.time()-start,2) ) ) print("***** omake *****") print( multiply(koyaku(yakusu4(6516516516),yakusu4(62565165190),[]),1) ) print(yakusu4(6516516516)) print(yakusu4(62565165190))

syntax2html