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

 

 

 

<코드>

import java.util.*;
public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int ans = 0;
		
		boolean check[] = new boolean[1001]; 
		for (int i = 0; i <= 1000; i++) {
			check[i] = true;
		}
		
		for (int i = 2; i <= Math.sqrt(1000); i++) {
			for (int j = i+i; j <= 1000; j += i) {
				check[j] = false;
			}
		}
		check[0] = false;
		check[1] = false;
		
		for (int i = 0; i < N; i++) {
			int x = sc.nextInt();
			if(check[x]) ans++;
		}
		
		System.out.println(ans);
	}
}

 

풀이 방법

에라토스테네스의 체를 이용해서 풀이를 하였습니다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

 

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

1978번: 소수 찾기