1-3. [구현] 수학

1. 진수변환 (2진수 문자열 => 10진수 => 2진수 문자열)

 

# 2진수 문자열을 10진수로 바꾸기

def b2d(num):
    a = list(map(int, num.replace('0b', '')))  # [1, 1, 0, 1]

    result = 0
    for x in a:
        result = result * 2 + x

    return result


print(int('0b1101', 2), b2d('0b1101'))  # 2진수 '1101' => 10진수 13


# 10진수를 2진수 문자열로 바꾸기

def d2b(num):
    a = []
    while num:
        a.append(num % 2)
        num //= 2

    a.reverse()  # [1, 1, 0, 1]

    return '0b' + ''.join(map(str, a))


print(bin(13), d2b(13))  # 10진수 13 => 2진수 '1101'

 

2. 거듭제곱

 

# 거듭제곱

def cpow(a, num):
    # 13 = 1101 (2진수)
    # a^13 = (a)^1 (a^2)^0 (a^4)^1 (a^8)^1

    rst = 1
    while num:
        if num % 2 != 0:
            rst *= a
        a *= a
        num //= 2

    return rst


print(3 ** 13, cpow(3, 13))  # 3의 13승 => 1594323

 

3. 소수 판정, 소수 찾기 

 

# 소수 판정

def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


print(is_prime(7))  # True


def is_prime2(n):
    i = 2
    while i * i < n:
        if n % i == 0:
            return False
        i += 1
    return True


print(is_prime2(7))  # True


# 모든 소수 구하기 (에라토네스의 체)

def era(n):
    primes = []
    check = [1] * (n + 1)  # 1이면 소수

    for i in range(2, n + 1):
        if check[i] == 0:
            continue

        primes.append(i)

        for j in range(i + i, n + 1, i):
            check[j] = 0

    return primes


def era(n):
    check = [1] * (n + 1)  # 1이면 소수
    check[0] = 0
    check[1] = 0

    for i in range(2, int(n ** 0.5) + 1):
        if check[i] == 1:
            for x in range(i + i, n + 1, i):
                check[x] = 0

    primes = [i for i, x in enumerate(check) if x == 1]
    return primes


print(era(7))  # [2, 3, 5, 7]