에라토스테네스의 체 소인수 분해1 에라토스테네스의 체를 활용한 소인수분해 어떠한 수 N을 수인수분해한다고 해보자. 예를들어 60 = 2 x 2 x 3 x 5 이다. 예를들어 입력값이 아래와 같다면 (첫번째 줄에 N = 소인수분해하려는 수의 갯수, 두번째 줄에 소인수분해하려는 수 kn / N은 1 ~ 1,000,000, kn은 2 ~ 5,000,000) N k1 k2 k3... 5 5 4 45 64 54 다음과 같이 각각 한줄로 소인수분해한 값을 출력해야 한다고 해보자. 5 2 2 3 3 5 2 2 2 2 2 2 2 3 3 3 기존에 생각했던 방식은 이하와 같았다. ('더보기') 더보기 내 경우 처음 생각한 방식은, 우선 입력값 N 이하의 모든 소수를 구해두고, 소수 리스트를 순회하며 찾는 방식이었다. 예를들어 N이 60이라면 60 이하의 모든 소수를 우선 구해둔다. 그 후 작.. 2024. 2. 23. 이전 1 다음
