hongminsung   11달 전

시간을 줄이는 방법을 모르겠습니다

ezh8n   11달 전

현재 N이하의 소수를 모두 구하는 방식이 O(N^2)입니다. 문제에서 주어지는 N의 크기는 최대 10,000,000로, 해당 코드는 당연히 주어진 시간 내에 통과할 수 없습니다. 소인수분해를 하기 위해 N이하의 모든 소수를 미리 구할 필요는 없습니다. 작은 수부터 sqrt(N)까지 차례대로 나누어 떨어지는지 확인하면, 자연스럽게 소수만 남게 됩니다.

댓글을 작성하려면 로그인해야 합니다.