안녕하세요,
재재입니다.
BOJ 16563 어려운 소인수분해 문제 풀이입니다.
BOJ 16563 어려운 소인수분해
(1) 문제 설명
분류 : math, 에라토스 테네스의 체
출처 : https://www.acmicpc.net/problem/16563
(1,000,000) 이하 N 이 주어지며,
이어서 (5,000,000) 이하의 N개의 숫자가 들어옵니다.
각 숫자에 대해 소인수 분해 결과를 오름차순으로 출력해주면 됩니다.
(2) 풀이 도출
boolean 배열과 에라토스 테네스의 체를 사용해서,
이 문제를 해결하려 한다면 시간초과를 받게 되는데요.
이 문제를 뒤집어서 풀어본다고 생각하면 좀 더 쉽게 접근할 수 있습니다.
소수를 사용해서 작은 숫자부터 하나씩 곱해가면서 숫자를 만들어나간다고 한번 생각해보고,
현재 숫자가 바로 어떤 숫자로 나뉘어지는지 정확하게 알 수 있다면 시간을 줄일 수 있습니다.
기존과 같지만 에라토스 테네스의 체를 (boolean 대신) int 배열로 생성하고,
배수를 체크하는 시점에 어떤 소수인지를 기록하면 됩니다.
(3) 정답 코드
BOJ 16563 어려운 소인수분해