
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)
'Algorithm > 이론' 카테고리의 다른 글
기약분수 만들기 (0) | 2023.01.11 |
---|---|
LIS 가장 긴 증가하는 부분 수열 (0) | 2022.10.06 |
그래프가 주어지는 유형 (0) | 2022.04.25 |
알고리즘 유형 6. 동적 계획법 (0) | 2022.04.24 |
알고리즘 유형 5. 이분 탐색 (0) | 2022.04.24 |

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)
'Algorithm > 이론' 카테고리의 다른 글
기약분수 만들기 (0) | 2023.01.11 |
---|---|
LIS 가장 긴 증가하는 부분 수열 (0) | 2022.10.06 |
그래프가 주어지는 유형 (0) | 2022.04.25 |
알고리즘 유형 6. 동적 계획법 (0) | 2022.04.24 |
알고리즘 유형 5. 이분 탐색 (0) | 2022.04.24 |