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

• 2부터 X-1까지 모두 나눠서 X가 소수인지 판별하는 문제 1

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

1. 문제

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

2. 문제 접근

1) 첫 줄에 수의 개수 N을 입력받는다.
2) N만큼 반복하며 주어진 수들을 받아서 이 중 소수의 개수를 계산하여 출력한다.

• 소수 찾기
  1) 미리 boolean형 배열에 소수인 것은 false, 소수가 아닌 것은 true로 계산하여 값을 넣는다.
  2) 에라토스테네스의 체 알고리즘을 사용하여 소수를 구한다.

  참고 https://velog.io/@agfalcon/%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

3. 코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        boolean num[] = new boolean[1001];
        num[1] = true;
        for(int i=2;i<=1000;i++) {
            if(num[i])
                continue;
            for(int j=i*2;j<=1000;j+=i) {
                num[j] = true;
            }
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        int count =0;
        for(int i=0;i<N;i++) {
            int t = Integer.parseInt(st.nextToken());
            if(!num[t])
                count++;
        }
        System.out.println(count);
    }
}