인프런 5.소수(에라토스테네스 체)_Java

Solution 1 

미리 배열을 만들고 인덱스를 값으로 넣어준다.

배수이면 0을 할당하는 방법으로 0이 아니면 소수라고 할 수 있다. 

 

private int solution(int n) {
        // 배열의 인덱스에 맞게 값으로 넣어준다.
        int[] a = new int[n+1];
        for (int i = 2; i <= n ; i++) {
            a[i] = i;
        }
        // 이미 지워진 숫자가 아니라면, 그 배수부터 출발하여, 가능한 모든 숫자 지우기
        // 2이라면 4부터, 3이라면 6부터 시작하고
        for (int i = 2; i <= n; i++) {
            if (a[i] == 0) continue; // 이미 지워졌다면 다음 반복으로
            for (int j = 2*i; j <=n ; j+=i) {
                a[j] = 0; // 배수 지우기
            }
        }
        int count = 0;
        for (int i = 2; i <=n ; i++) {
            if (a[i] != 0) count++; // 지워지지 않았다면 소수이다.
        }
        return count;
    }

Solution 2 (강사님 풀이)

개념은 비슷한 거 같은데 간결하다. 

private int solution(int n) {
        int count = 0;
        int[] ch = new int[n + 1];
        for(int i=2; i<=n; i++) {
            if (ch[i]==0) {
                count++;
                for (int j = i; j<= n; j+=i){
                    ch[j] = 1;
                }
            }
        }


        return count;
    }