マスター・オブ・整数で競技プログラミング その2
2 素因数分解の利用 素因数の個数
2で割り切れる回数
- (1)Pが2で何回割り切れるか。
愚直な実装をすれば,素直に2で割り続ければよい。
def func(n): if n == 1: return 1 return n*func(n-1) N = int(input()) P = func(N) cnt = 0 while P >= 1: if P % 2 == 0: P //= 2 cnt += 1 else: break print(cnt)
ちなみに,
N = 100 P = func(N) print(P) --->P = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
であり,N=100程度でもP=N!はけっこう大きい数(158桁)である。
また,N!は再帰関数を用いなくても単純にループ処理でよい。
P = 1 for i in range(1,N+1): P *= i
しかし,愚直に割り算を繰り返す方法だと2で割り切れる回数だけ計算を行うことになり,効率が悪い。「2で1回割り切れる」=「素因数として2を1つ含む」と考える。すると「2でn回割り切れる」=「素因数として2をn個含む」となることがわかる。つまり,P=N!について素因数2の個数を調べればよい。 たとえば,N=100として考える。1から100までのそれぞれの自然数に含まれる素因数2の個数と,1から100までの自然数の積に含まれる素因数2の個数は等しいので(これ重要),1から100それぞれの数について素因数2の個数を数えてそれを合計すればよい。明らかにすべての偶数(2,4,8,10,,,,,48,50)は素因数2を含んでいるので,50個は素因数2が含まれていることがわかる。この50個という数は,100÷2=50として求められる。
しかし,4や8はそれぞれ2の2乗,2の3乗なので,4は素因数2を2個,8は3個含んでいるため,このような数について考慮する必要がある。したがって,100÷(2の2乗)=25であることから,素因数2を2個含む数は100までに25個あることがわかる。同様に素因数2を3個含む数は100÷(2の3乗)= 12 あまり4なので,12個。このように考えていくと
と求めることができる。
N = int(input()) ans = 0 i = 1 while N//(2**i) >= 1: ans += N //(2**i) i += 1 print(ans)
- (2)また,Pの末尾に(10進法で)0がいくつ続けて並ぶか。 これは(1)の応用である。末尾に0が来るということは10で割り切れるということであり,それは素因数として2と5を1つ含んでいるということである。したがって,(1)と同様に素因数5の個数を数えてが答えである。さらにをとらなくても,そもそも素因数2の個数と素因数5の個数では素因数5の個数の方が少ないのは明らかなので,最初から素因数5の個数を答えとしてしまってよい。
#2**iを5**iに変更しただけ N = int(input()) ans = 0 i = 1 while N//(5**i) >= 1: ans += N //(5**i) i += 1 print(ans)