백준 1978번
https://www.acmicpc.net/problem/1978

---

문제

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

---

입력

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

---

생각하기

첫번 째 삽입되는 숫자로 판단해야 할 숫자의 개수를 파악하고 변수loop로 지정해주었다.
(변수의 개수 만큼 반복)

다음은 List를 생성 후 변수들을 모두 삽입해줍니다.
(일반 Array 사용하셔도 괜찮습니다. 저는 List를 선호해서 사용했습니다.)

이제 판단할 숫자를 하나씩 꺼내서 소수인 숫자들만 세아려주면된다.
prime_Number 변수를 소수의 개수를 저장할 변수로 만들어 주고, 가장 먼저 1은 소수가 아니기때문에 예외로 생각해서 if문으로 continue 를 설정해 지나치도록 해주었다.

그리고 숫자가 소수인지를 판단할 때는 에라토스테네스의 체를 사용하도록 했다.
에라토스테네스의 체는 해당 숫자를 100이라고 가정했을 때, 100의 루트를 씌운 값 인 10까지만 배수를 찾으면 되는 소수를 찾을 때 아주 효율적인 방법이다.
sqrt 변수의 값이 10이 되는 것이다.

먼저 소수가 아닐 경우의 동작이다.
100을 기준으로 보면 sqrt는 10(100의 루트값)이 되어,j는 2부터 10까지 반복한다.
2일 경우에 2의 배수인지 검사하는 것이다. 여기서 2와 100을 나누면 나머지가 0이기 때문에 2의 배수에 해당되면서 소수가 아님을 의미하게 된다.

이런 경우는 굳이 3,4.. 뒤의 배수들을 검사 할 필요가 없기 때문에 한번이라도 나머지가 0이 되면 바로 break로 List에 있는 다음 숫자를 검사하도록 한다.

이번엔 소수일 경우의 동작을 살펴보자.
만약 소수인 17일 경우 temp값이 17이 되고 sqrt는 4가 된다.
이렇게되면 17이 2, 3, 4의 배수인지 반복해서 검사해서 나머지를 찾으면 된다.

j가 2,3,4를 반복해서 17과 나누어서 나머지가 0인 경우가 있는지 검사한다 하지만 2, 3, 4의 배수가 아니기 때문에 반복문을 모두 마치게 되는데 이때 sqrt == j 의 조건에 부합하면 j 반복문을 모두 마쳤을 때 소수가 맞음을 알게되고 prime_Number를 증가시켜 소수의 개수를 하나 증가시키게 된다.

이런식으로 반복해서 소수의 개수를 구할 수 있다.

TMI

백준 '소수 구하기' 문제를 푼지 2일도 채 안되서, 다시 소수 문제가 나왔다..
이제 소수라면 진절 머리가 날 정도다..

근데 이렇게 반복하면 정말 도움이 많이 된다는 걸 알기 때문에 마음을 다잡고 했는데, 이상하게 전에 소수 구하기 문제 보다 쉽다는 생각이 들었다.

확실히 '소수 구하기' 문제에서 고생한 보람이 있는지 에라토스테네스의 체를 활용해서 쉽게 해결할 수 있었다.

고마워요 에라토스테네스!

당신의 친절한 이웃
-에라토스테네스-

(스파이더맨 아님 기분탓임)

---

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;	
		int loop = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());

		List<Integer> list = new ArrayList<>();
		for(int i=0; i<loop; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}

		int prime_Number = 0;
		for(int i=0; i<loop; i++) {
			// 소수의 개수
			int temp = list.get(i);		

			// 1은 소수가 아니기 때문에 건너뜀.
			if(temp == 1) {
				continue;
			}
			else {
				int sqrt = (int) Math.sqrt(temp);

				// sqrt 1은 무조건 소수임(2와 3이 해당).
				if(sqrt == 1) {
					prime_Number++;
				}
				else {
					for(int j=2; j<=sqrt; j++) {

						if(temp % j == 0) {
							// 한번이라도 나머지가 0이 걸리는 게 있다면 소수가 아니기때문에 out	
							break;
						}

						if(j == sqrt) { {
							// 소수임
							prime_Number++;
						}
					}
				}
			}

		}
		System.out.println(prime_Number);
	}
}