[BOJ/Step9] 1978 : 소수 찾기 (JAVA)

www.acmicpc.net/problem/1978

1978번: 소수 찾기

---

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

4

1 3 5 7

 

예제 출력 1

3

---

풀이

1. 주어지는 수가 1000 이하의 자연수이므로 1~1000 사이의 소수를 미리 계산하여 배열에 넣어둔다

   1-1. 소수는 1과 자기 자신으로만 나눠지는 수이므로, 2, 3, 5, …… 순이다.

   1-2. 2와 3부터 배열 prime[] 에 넣어두고

   1-3. 4~1000 의 수가 해당 prime의 수로 나누어지는지 확인하여 나누어지지 않는 수만 prime에 추가한다.

2. 입력받은 수가 prime에 존재하는지 확인하여 존재할 때만 count++

3. count를 출력

 

import java.util.Scanner;

public class B1978 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		int count = 0;
		
		int prime[] = new int[200];
		int primeIdx = 1;
		prime[0] = 2;
		prime[1] = 3;
		
		Loop1 :
		for(int i = 4; i <= 1000; i++) {
			for(int j = 0; j < primeIdx; j++) {
				if(i % prime[j] == 0) {
					continue Loop1;
				} else {
					
				}
			}
			prime[++primeIdx] = i;
		}
		
		for(int i = 0; i < t; i++) {
			int num = sc.nextInt();
			for(int j = 0; j <= primeIdx; j++) {
				if(prime[j] == num) {
					count++;
					break;
				}
			}
		}

		System.out.println(count);
	}
}