문제 : boj11653
소수들로 소인수 분해 후 그 결과를 오름차순으로 출력하면 되는 문제이다. 바로 생각날 부분은 우선 소인수 분해를 위한 소수를 구하기 위해 에라토스테네스의 체를 사용해 N이하의 소수를 구한 후, 작은 소수부터 차례대로 나눠보면서 나눠지면 출력하는 방식이다.
하지만 에라토스테네스의 체를 계산하는데도 사실 O(N)정도의 시간이 필요하며, 이 문제에서는 N이 하나만 주어지므로 굳이 사용하지 않아도 된다. 만약 TC가 여러개였다면 물론 미리 소수를 구해두는게 이득이었을 것이다. 이 문제의 경우 그냥 2부터 N까지의 수로 직접 N을 나눠보면서 나눠지는 수를 출력하기만 하면 된다.
코드 : github
import sys
input = sys.stdin.readline
n = int(input())
for i in range(2, n+1):
while n%i == 0:
print(i)
n//=i
if n==1:
break
'PS > BOJ' 카테고리의 다른 글
백준 6219 자바 - 소수의 자격 (BOJ 6219 JAVA) (0) | 2022.02.12 |
---|---|
백준 2358 자바 - 평행선 (BOJ 2358 JAVA) (0) | 2022.02.11 |
백준 13211 자바 - Passport Checking (BOJ 13211 JAVA) (0) | 2022.02.10 |
백준 1544 자바 - 사이클 단어 (BOJ 1544 JAVA) (0) | 2022.02.09 |
백준 18126 자바 - 너구리 구구 (BOJ 18126 JAVA) (0) | 2022.02.08 |
댓글