강의로 돌아가기
우성환

에라토스테네스의 체 알고리즘을 써도 효율성 테스트를 통과하지 못하네요...

왜그러는 걸까요....

작성중인 코드―Solution.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;
class Solution {
  public int solution(int n) {
      int answer = 0;

        List<Boolean> list = new ArrayList<Boolean>(); 

        list.add(false);//0과 1은 소수가 아니다라고 박자.
        list.add(false);

        //모든 공간 초기화
        for(int i =2; i<=n; i++) {
            list.add(true);
        }

        for(int i =2; (i * i) <= n; i++) {
            if(list.get(i)) { //소수면 소수의 배수는 없앤다.
                for(int j = i *2; j<= n; j+=i) {
                    list.set(j, false);
                }
            }
        }
        for(int i =0; i<list.size();i++) {
            if(list.get(i))
                answer++;
        }
        return answer;
   }
}
1 개의 답변
김도형

곱하는 것은 오히려 효율성을 떨어트립니다. Math.sqrt()를 사용해보세요.

  • 우성환

    두번쨰 포문을 for(int i =2; i <= Math.sqrt(n); i++) 로 했는데도 안되네요 ㅠㅠ 답답하네요ㅠㅠ

    우성환―2019.10.22 22:07
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.