소스가 잘 이해되지는 않지만,
예를 들어 어떤 자연수 N이 소수인지 판별하기 위해서는,
2부터 N-1까지 다 나누어보면서 확인하는 방법도 있겠지만,
2부터 sqrt(N)까지만 검사하는 방법도 있습니다.
이 방법이 되는 이유는 귀류법으로 증명할 수 있습니다.
이를 그대로 구현하면, 시간복잡도는 O(sqrt(2) + sqrt(3) + ... + sqrt(N)) => O(N log N) 정도 됩니다.
제 생각이지만, 위에 있는 소스는 O(N^2)가 아닐 듯 싶네요.
쓰다보니 알았는데, N의 정의를 적지 않았다...
ijm91 8년 전
에라토스테네스 이용해서 했는데시간초과뜨네요..ㅠㅠ
if(i<a) 이건 3 16 입력했을때, 2까지 소수로 담아버려서.. 그거 구분하려고 했습니다..
근데 이걸 붙이면 시간초과가 뜨고,
저 분기문을 빼면 출력초과가 뜨네요.. 어디가 잘못된걸까요??
밑에 for 문돌린거 안으로 넣어줘도 출력초과가...ㅠㅠ