펭로그

문제링크 : https://boj.kr/11653 어떤 숫자의 소인수들은 소수들의 곱으로 표현할 수 있다.그러기 위해선 입력 숫자의 범위만큼 소수 리스트를 구해서 해당 소수들이 입력 숫자로 나누어 떨어지는지를 계산하고 이를 무한히 반복하여 더이상 나누어 떨어지지 않을 때까지 나누면 된다. 다만, 소수 리스트를 다 구할 필요는 없고 입력 숫자의 제곱근 범위까지만 구하면 된다.제곱근보다 큰 범위의 숫자를 2개 이상 서로 곱하면 입력 숫자를 초과하기 때문에 더 이상 구할 필요가 없다.소수 리스트에 속하지 않은 남은 숫자는 무조건 소수이다. (해당 숫자가 소수 리스트의 곱으로 표현되는 순간 소수가 아니다.) 소수 판별은 에라토스테네스의 체를 이용하여 구하면 더 빠르게 구할 수 있다. 123456789101112..