[JAVA] 백준 1978번 : 소수 찾기

 

---

 

• 생각

저번 주에 풀었던 문제 중 소수찾기할 때 에라토스테네스의 체를 이용하여 찾았다. 이번 문제에서도 에라토스테네스의 체를 사용해서 풀어보면 좋을 것 같아서 풀어보았다.

 

• 코드

정답 코드 : 에라토스테네스의 체를 이용해 소수가 아닌 수 들을 true로 변경 해준다. 배열 중 false인 수들은 소수이다.

 

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

public class Main {
	static int N, count;
	static boolean[] check;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(count);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		N = Integer.parseInt(br.readLine());
		check = new boolean[1001];
		count = 0;
		
		check[0] = check[1] = true;
		for (int i = 2; i <= 1000; i++) {
			if (check[i] == true) {
				continue;
			}
			// 해당 수로 나누어 떨어지는 수는 소수이므로 true로 check
			for (int j = i + i; j <= 1000; j+=i) {
				check[j] = true;
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			if(!check[Integer.parseInt(st.nextToken())]) count++;
		}
	}

}