choisb7   4년 전

어느부분에서 시간초과가 뜨는지 모르겠습니다.

pichulia   4년 전

최대값이 1,000,000,000,000 일 때 klist에 값이 얼마나 많이 들어가는지 확인해보셨나요 ㅠㅠ

999999000000 1000000000000

위 데이터에 대해서 테스트해보시길 바랍니다.

choisb7   4년 전

소수 구하는 부분에서는 klist를 구하는데  999999000000에 대해서는 0.683초 정도가 걸리고  1000000000000에 대해서는 0.75초 정도가 나왔습니다. 여기서는 시간 문제가 없었고, 범위내의 모든 값에 대해서 제곱수가 아닌수를 찾는데에 시간이 오래 걸림을 확인했습니다.

새로운 접근이 필요하다고 생각하여 범위내의 모든 i에 대해서 제곱수가 아닌수를 찾는 방법이 아닌 범위내의 수 중에서 klist 내의 소수 제곱수의 배수가 되는 수를 제거하는 방법을 사용하였는데 이것도 시간이 오래 걸립니다. 더 좋은 방법이 있을까요? 

pichulia   4년 전

kk를 구하는 부분이 시간초과의 원인으로 보입니다. for po를 돌지 않고 kk를 구할 수 없는지 고민해보시기 바랍니다.

choisb7   4년 전

감사합니다. 풀었습니다. ^^

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