#1978 : 소수 찾기

풀이방법

사용된 것:

수학

에라토스테네스의 체

 

2022.04.17

에라토스테네스의 체의 방식으로 1부터 1000까지의 모든 소수를 구해둔 다음,

구해둔 소수 목록을 이용하여 입력으로 주어지는 수들이 소수인지를 판별하면 된다.

 

코드

Java(2022.04.17)

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

public class Main {
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//2부터 1000까지의 소수를 모두 구해놓기
		
		int[] primes = new int[1001];
		//모든 값을 1로 초기화한 후, 소수가 아닌 수의 인덱스에 저장된 값을 0으로 변경할 것
		Arrays.fill(primes, 1);	
		primes[0] = 0;
		primes[1] = 0;	//0과 1은 소수가 아니므로 값을 0으로 지정
		
		//2부터 1000까지의 모든 수에 대하여
		for(int i = 2; i<1001; i++) {
			//i가 이미 소수가 아닌 것으로 판별난 수라면
			//이 수와 이 수의 배수들도 모두 판별이 끝났으므로 continue
			if(primes[i] == 0) continue;
			
			//i가 소수라면
			//이 수의 모든 배수들에 대하여 저장된 값을 0으로 변경
			for(int j = 2; i*j<1001; j++) {
				primes[i*j] = 0;
			}
		}
		
		//입력값 받아오기
		int n = Integer.parseInt(br.readLine());
		int cnt = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i<n; i++) {
			int temp = Integer.parseInt(st.nextToken());
			if(primes[temp] == 1)cnt++;
		}
		
		//정답 출력
		System.out.print(cnt);
	}

}