코드노예

* 이 포스트는 "파이썬 프로그래밍으로 지루한 작업 자동화하기" 의 내용을 참조해서 작성하였습니다.

* 파이썬 3.3을 기준으로 작성하였습니다.

수학 연산자 (우선순위 순)

기본 자료형

정수, 부동소수점 숫자, 문자열

문자열 연산

문자열 합

>>> 'Hello' + ' ' + 'World'

'Hello World'

문자열 곱 (정수만 가능)

>>> 'Hello' * 3

HelloHelloHello

문자열에 숫자를 연결하려면, 숫자를 명시적으로 형변환해야 한다.

>>> 'Hello' + str(123)

Hello123

변수 이름 규칙

- 한 단어로 되어야 함

- 문자, 숫자, 밑줄 문자 사용 가능

- 첫 글자는 숫자여서는 안됨

기본 함수

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

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

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

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