na1st   3년 전

시간초과 계속나와열!흑흑.. 자바의 길은 험난해요 ㅠㅠ


gallopsys   3년 전

지금 소수 구하는 알고리즘이 대략 O(n2)의 시간복잡도가 나옵니다. 최악의 경우 대략 1012초 정도로 대략 109번의 루프에 1초가 소요된다고 하면, 1000초, 즉, 분 단위까지 소요될 수 있습니다.

이를 해결하기 위해 한 번 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해서 구해보세요.

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