백준 1978번 : 소수 찾기

백준 1978번 : 소수 찾기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Boolean[] booleans = new Boolean[1001];
        Arrays.fill(booleans, false);
        booleans[1] = true;
        for(int i=2; i<booleans.length/2; i++){
            for(int j=2; j*i<booleans.length; j++){
                booleans[j*i] = true;
            }
        }

        int count = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int resultCount = 0;
        while(count-->0){
            int index = Integer.parseInt(st.nextToken());
            if(booleans[index]!=true){
                resultCount +=1;
            }
        }
        System.out.println(resultCount);
    }
    public static void main(String args[]) throws IOException {
        new Main().solution();
    }
}

에라토스테네스의 체를 가장 먼저 떠올렸고, 처음엔 배열을 숫자로 초기화 해서 배수의 값들을 지우려고 했는데, 숫자를 0으로 바꾸어준다거나 해주어야 하는게 의미가 명확하지 않아서 boolean으로 문제를 해결했다.

 

풀이 결론

모든 배열의 값을 false로 초기화 해준 후

소수가 아닌 1은 true 변경 해주고,

자연수 1000까지 브루트포스로 2,3을 제외한 낮은 수의 배수부터 true로 값을 변경 해준다.

2x2 = 4 = true .. 2x16 = 32 = true

3x2 = 6 = true .. 3x16 = 48 = true

그럼 결국 소수인 것만 false로 유지하게 되고,

while문으로 count 만큼 돌려서 입력받은 배열의 인덱스의 값이 false일 경우 count 해준다.

그리고 출력.