wkddbwls4982   2년 전

무한 루프를 쓰지 않고 이중 for문을 이용해서 문제를 풀었는데 시간초과라고 뜹니다...

해결할 방법이 없을까용ㅠㅠㅠㅠㅠ 도와주세요

chogahui05   2년 전

이중 for문을 도니까 시간 초과가 뜨지요.. O(n)도 시간초과 뜨는데

O(n^2)는 말할 것도 없겠죠.


O(root(n))만에 해결할 수 있는 방법을 찾아봅시다.

jyuno426   2년 전

1. n 이하의 자연수 중, n과 서로소인 수의 갯수를 구하는 오일러 피 함수
2. 소인수분해를 sqrt(n) (루트 n)의 시간복잡도로 하는 방법

위 두가지를 공부하시면 문제를 푸실 수 있습니다!

https://ko.wikipedia.org/wiki/...

https://ratsgo.github.io/data%...

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