알고리즘 유형 7. 소수

 

N이 소수인지 판별하기

- 2부터 루트 N ​까지의 수로 모두 나누어 보고, 한 번이라도 나누어 떨어지면 소수가 아닙니다.

- 반복문을 빨리 돌기 위해서는 2부터 루트 N 까지의 수들 중 (2를 포함한)홀수 또는 소수로만 나누는 방법을 생각할 수 있습니다.

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

 

 

 

 

N보다 작은 소수 구하기

에라토스테네스의 체 알고리즘을 사용합니다.

 

1단계)

N + 1 크기의 chk 배열을 만들고 True로 초기화합니다.

True는 이 수가 소수가 맞다는 의미입니다.

 

2단계)

2부터 루트 N까지의 수들 중 소수(chk[i] == True)만 차례대로 탐색합니다.

 

3단계)

현재 탐색중인 수의 배수들은 전부 chk 값을 False로 체크합니다.

어떤 수의 배수이므로 소수가 아닙니다.

 

4단계)

탐색 종료 후, 2부터 N까지의 수들 중 chk 값이 True로 남아있는 수들이 소수입니다.

chk = [True] * (N + 1)

for i in range(2, int(N ** 0.5) + 1):
    if chk[i]:
        for j in range(i + i, N + 1, i):
            chk[j] = False

prime = [i for i in range(2, N + 1) if chk[i]]

 

 

 

 

 

N을 소인수분해하기

1단계)

루트 N 이하의 소수들을 모두 구합니다.

에라토스테네스의 체 알고리즘 사용합니다.

 

2단계)

N을 앞서 구해 놓은 소수들을 가지고 나눌 수 있을 때까지 계속 나눕니다.

이 때 N을 나누는 데 쓰인 수들은 전부 N의 소인수입니다.

 

3단계)

2단계 나누고 남은 값은 1이거나, 루트 N 이하의 소수로도 나눌 수 없었던 루트 N 초과의 소수입니다.

남은 값이 1이 아니라면, 그 값을 마지막 소인수로 추가해줍니다.

 

N = int(input())

# M(루트 N) 이하의 수들 중 소수를 찾는다.
M = int(N ** 0.5) + 1
chk = [True] * (M + 1)

for i in range(2, int(M ** 0.5) + 1):
    if chk[i]:
        for j in range(i + i, M, i):
            chk[j] = False

prime = [i for i in range(2, M + 1) if chk[i]]

# 앞서 구한 소수들을 가지고 N을 나눌 수 있을 때까지 계속 나눈다.
i = 0
while i < len(prime) and N >= prime[i]:
    if not(N % prime[i]):
        N //= prime[i]
        print(prime[i])
    else:
        i += 1

# 나누고 남은 값은 1이거나 M(루트 N) 초과의 소수이므로, 남은 값이 1이 아닐 시 마지막 소인수로 추가해준다.
if N != 1:
    print(N)