코드노예

보통 팩토리얼의 경우 숫자가 너무 커지기 때문에 정확한 값을 계산할 수 없는 경우가 많습니다.

하지만 팩토리얼 값을 소인수 분해했을 때, 지수가 어떻게 되는 지는 계산이 가능합니다.

다음 링크에서 자세한 설명을 보실 수 있습니다.

https://janmr.com/blog/2010/10/prime-factors-of-factorial-numbers/

특정 소수에 대한 지수를 계산하는 코드는 다음과 같습니다.

import math

def factorialExp(n, p):
    tRet = 0
    tVal = int(math.log(n, p))
    for i in xrange(1, tVal+1):
        tRet += n // p**i
    return tRet

소수 계산과 함께 많이 쓰이는 오일러 피 함수 입니다.

피 함수는 자신보다 작은 양수 중에서 자기 자신과의 최대 공약수가 1인 숫자가 몇 개인지를 나타냅니다.

따라서 소수 p의 경우 모든 숫자가 서로 소 이기 때문에 다음과 같이 쓸 수 있습니다.

φ(p) = p - 1

그리고 p와 q가 서로 소인 경우 다음과 같은 식이 성립합니다.

φ(pq) = φ(p)φ(q)

자세한 설명은 다음 링크를 참고하세요.

https://en.wikipedia.org/wiki/Euler%27s_totient_function

def totient(n):
    phi = int(n > 0 and n)
    for p in range(2, int(n ** .5) + 1):
        if not n % p:
            phi -= phi // p
            while not n % p:
                n //= p
    if n > 1: phi -= phi // n
    return phi

수학에서 에라토스테네스의 체는 소수를 찾는 방법입니다. 고대 그리스 수학자 에라토스테네스가 발견하였습니다.

방법은 다음과 같습니다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다.

2. 2는 소수이므로 소수 리스트에 적어두고,

3. 자기 자신을 제외한 2의 배수를 모두 지웁니다.

4. 남아 있는 수 가운데 3은 소수 이므로 소수 리스트에 적어두고,

5. 자기 자신을 제외한 3의 배수를 모두 지웁니다.

6. 위의 과정을 반복하면 구하는 구간의 모든 소수를 찾을 수 있습니다.

다음은 파이썬을 이용한 예시이며, 소수인지를 체크할 수 있는 배열 정보와 소수 리스트를 리턴해 줍니다.

def findPrimes(n):
        tPrimes = [2]
        tArr = [True] * (n+1)
        tArr[0], tArr[1] = [False] * 2

        for i in xrange(4, n+1, 2):
                tArr[i] = False

#        for i in xrange(3, n+1, 2):
#                j = 3
#                while True:
#                        tmp = i * j
#                        if (tmp > n):
#                                break
#                        tArr[tmp] = False
#                        j += 2

        for i in xrange(3, int(n**0.5)+1, 2):
            if (tArr[i]):
                for j in xrange(i**2, n+1, 2*i):
                    tArr[j] = False

        for i in xrange(3, n+1, 2):
                if (tArr[i]):
                        tPrimes.append(i)

        return tArr, tPrimes