Baekjoon1978: 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

 

추상화

역시 제한조건이 중요하다. 수의 크기는 1,000이하의 자연수이다
미리 배열을 통해 소수를 가려낼 수 있다
1) 논리배열을 만든다. 처음 값은 모두 false이다
2) 소수가 아닌 숫자를 true로 만들어준다
3) 어떤 숫자에 2, 3 등을 곱한 결과값은 소수가 아니다
4) 반복문 안에서 모든 숫자에 대해 값을 곱하고 해당값을 논리배열에 표시해준다
5) 소수인지 묻는 입력값에 대해 해당하는 값을 논리배열 index와 대조하여 답을 구한다 

import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException{
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	 boolean[] prime = new boolean[1001];
	 int devide =0;
	 int num = 0;
	 int sum=0;
//소수 배열 만들기, 반복문에서 사용되는 변수 미리 만들기
	 for(int i=2; i<1001; i++) {
		 devide = 1000/i;
		 for(int j=2; j<=devide; j++) {
			 prime[i*j] = true;
//false로 남은 애들만 소수다. 2부터 곱해주는 것을 잊지말자
		 }
	 }
	 prime[0] = true;
	 prime[1] = true;
//0과 1은 특별히 구분해서 소수가 아님을 표시한다
	 int N = Integer.parseInt(br.readLine());
	 StringTokenizer st = new StringTokenizer(br.readLine()," ");
	 for(int i=0; i<N; i++) {
		 num = Integer.parseInt(st.nextToken());
		 if(prime[num]==false) {
			 sum++;
//받은 입력값 num이 배열에서 false값이면 소수이므로 개수를 추가한다
		 }
	 }
	 System.out.println(sum);
}
}