팩토리얼이 어떤 수로 나누어 떨어지는지 확인하기

어떤 정수 f의 팩토리얼이 다른 정수 n 으로 나누어 떨어지는지 확인하기.

1 x 2 x .. x f / n 를 손으로 계산할 때, 팩토리얼부터 구하지 않을 것. 분명 분모와 2를 약분하고, 분모와 3을 약분하고 ... 를 반복하는 방식으로 풀 것이다. 이 과정을 코드로 옮겨 봄.

from functools import lru_cache


@lru_cache(None)
def gcd_r(b, s):
    if b < s:
        b, s = s, b
    b, s = s, b%s
    if s == 0:
        return b
    return gcd_r(b, s)


def gcd(b, s):
    if b < s:
        b, s = s, b
    while True:
        b, s = s, b%s
        if s == 0:
            break
    return b


def fac_divisible_check(f, n):
    """
        checks if f! disivible by n


         f!    1 x 2 x 3 x... x f   
        --- = -------------------- =
         n            n             

            /////////////////////////////
            // if n is even number
            // 2 --> 1, n --> n'(=n//2)
            /////////////////////////////

               1 x 1 x 3 x ... x f
            = --------------------
                      n'


        do this for each factor.        

        if n' reduces to 1, f! divisible.
        if not, f! not divisible.
    """

    for i in range(2, f+1):
        n //= gcd(i, n)
        if n == 1:
            return True
    return False


test_cases = [ [6, 9], [6, 27], [20, 10000], [20, 100000], [1000, 1009], [200, 23821] ]

for f, n in test_cases:
    if fac_divisible_check(f, n):
        print('{}! is divisible by {}.'.format(f, n))
    else:
        print('{}! is NOT divisible by {}.'.format(f, n))