[Java] 소수 찾기 (백준 1978번)

📖문제

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

• 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
• 주어진 수들 중 소수의 개수를 출력한다.

---

✏️내 풀이

💡첫 번째 생각

1. N을 입력받는다.
2. 길이가 N인 배열을 생성하고
3. 입력값을 공백으로 구분해서 배열에 넣는다.
4. 소수의 개수를 의미하는 변수 num을 선언한다.
5. 소수 구하기를 N번 반복한다.
   • 소수 구하기
     5-1. 정수를 n이라고 했을 때, n을 2부터 (n-1)번째 수로 반복해서 나눈다.
     5-2. 나머지가 0이면 소수가 아니다.
     5-3. 끝까지 나머지가 0인 경우가 없으면 소수다.
     5-4. 만약 소수라면 num++을 한다.
6. num을 출력한다.

package lv_1;

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

public class B1978 {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//n을 입력받는다.
		int n = Integer.parseInt(br.readLine());

		//길이가 n인 배열 생성
		int[] arr = new int[n];

		//입력값을 공백으로 구분
		StringTokenizer st = new StringTokenizer(br.readLine());

		//입력값을 배열에 저장
		for(int i=0;i<arr.length;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int num = 0;
		int count = 0;

		//값 하나씩 소수 검증 (i = 배열에 저장된 입력값 인덱스)
		for(int i=0;i<arr.length;i++) {

			//소수구하기
			//값을 2~(n-1)번째 값으로 계속 나눈다.
			for(int j=2;j<=arr[i]-1;j++) {
				if(arr[i]%j==0) { //만약 나눈 나머지가 0이면 j는 arr[i]의 약수
					count++;
					break; //소수가 아닌 것이 확정되면 for문을 빠져나와서 그 다음 입력값으로 넘어감
				}
			}

			if(arr[i]!=1 && count==0) {
				num++;
			}
		}

		System.out.println(num);
	}
}

세 번 틀리고.. 알고리즘 책의 도움을 받기로 결정..
이건 틀린 답입니다.. 아래에 맞는 답 있음

💡두 번째 생각

방법은 💡첫 번째 생각과 같다. 다만 소수구하기 부분 코드가 다름

package lv_1;

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

public class B1978 {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//n을 입력받는다.
		int n = Integer.parseInt(br.readLine());

		//길이가 n인 배열 생성
		int[] arr = new int[n];

		//입력값을 공백으로 구분
		StringTokenizer st = new StringTokenizer(br.readLine());

		//입력값을 배열에 저장
		for(int i=0;i<arr.length;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int num = 0;

		//값 하나씩 소수 검증 (i = 배열에 저장된 입력값 인덱스)
		for(int i=0;i<arr.length;i++) {

			int j;

			//소수구하기
			//값을 2~(n-1)번째 값으로 계속 나눈다.
			for(j=2;j<arr[i];j++) {
				if(arr[i]%j==0) { //만약 나눈 나머지가 0이면 j는 arr[i]의 약수
					break; //소수가 아닌 것이 확정되면 for문을 빠져나와서 배열의 다음 입력값으로 넘어감
				}
			}

			//나머지가 0인 경우가 끝까지 없으면 j는 ++된 상태로 for문이 끝난다.
			//때문에 j=arr[i]인 경우가 발생한다.
			//이는 마지막까지 나누어 떨어지는 수가 없음을 의미하며, arr[i] 데이터가 소수임을 뜻한다.
			if(arr[i]==j) {
				num++;
			}
		}

		//정답 출력
		System.out.println(num);
	}
}

if(arr[i]==j) {num++;}
이 코드 한 줄을 찾는 길이 멀고도 험난했다..

---

🤓배운 점

소수 나열하기

• 소수
  자신과 1 이외의 어떤 정수로도 나누어 떨어지지 않는 정수이다.
  2부터 (n-1)까지의 어떤 정수로도 나누어 떨어지지 않는다.
  만약 나누어 떨어지는 정수가 하나 이상 존재하면 그 수는 합성수이다.

소수를 구하는 부분은 이중 for문이다.

for(int i=0;i<arr.length;i++) {

	int j;

	for(j=2;j<arr[i];j++) {
		if(arr[i]%j==0) {
			break;
		}
	}

	if(arr[i]==j) {
		num++;
	}
}

안쪽 for문 종료된 시점에서 변수 j의 값은 다음과 같다.

• arr[i]가 소수인 경우 : arr[i] = j -> for문이 끝까지 실행됨
• arr[i]가 합성수인 경우 : arr[i] > j -> for문이 중간에 중단됨