백준 1978: 소수찾기(JAVA)

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

이전 소수 관련 문제 풀이와 비슷하다. 1000이하의 자연수에 대해 판별하는 것이기 때문에 1부터 1000까지 소수인지 아닌지를 미리 구해주고 prime이라는 boolean 배열에 담아준다. 2부터 1000까지 배수인 것을 소수가 아니라고 표시한다. 아래 코드에서는 prime[i]가 false이면 i는 소수이다.

 

import java.util.*;

public class Main {
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		int N;
		int a, cnt=0;
		
		boolean[] prime = new boolean[1001];
		prime[1] = true;
		
		for(int i=2; i<1001; i++) {
			if(prime[i])
				continue;
			
			for(int j=2; i*j<1001; j++)
				prime[i*j]=true;
		}
		
		N=sc.nextInt();
		for(int i=0; i<N; i++) {
			a=sc.nextInt();
			if(!prime[a])
				cnt++;
		}
		
		System.out.println(cnt);
	}
}