🥉 [Baekjoon / Java] 1978. 소수 찾기

문제 설명

💡 Info

• 난이도 : 브론즈 II
• 시간 제한 : 2초
• 메모리 제한 : 128MB
• 백준 링크: https://www.acmicpc.net/problem/1978
• 풀이 링크(GitHub): hayannn/CodingTest_Java/백준/Bronze/1978. 소수 찾기

내용

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

📥입력 조건

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

4
1 3 5 7

📤출력 조건

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

3

문제 이해

• 소수의 개수를 세서 출력하기

알고리즘

실제 풀이 시간 : 10분

• 입력
  • N 입력받기
  • N개의 수인 arr 입력받기
• 계산
  • 1과 자기 자신만을 약수로 가지는 수인 “소수”인 수만 저장하기
    • N % N == 1인 수
• 출력
  • 소수 출력하기

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] arr = new int[N];
		int count = 0;
		
		for(int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		for(int i=0; i<N; i++) {
			if(arr[i] == 1) count++;
			if(arr[i] % N == 1) count++;
		}
		System.out.println(count);	
	}
}

오답 체크

• 1은 소수에 해당되지 않는데, 이를 포함하는 문제 발생
• 또한, 2번째부터 소수인지 판별하는데 변수인 primNum을 추가
  • primeNum이 0인 경우는 즉, 소수인 경우를 뜻하기 때문에 count를 증가시키는 것으로 해결

//before
for(int i=0; i<N; i++) {
	if(arr[i] == 1) count++;
	if(arr[i] % N == 1) count++;
}
System.out.println(count);	

//after
for(int i=0; i<N; i++) {
	if(arr[i] == 1) continue; //1은 소수에서 제외시키기
	
	int primNum = 0;
	
	for(int j=2; j<arr[i]; j++) {
		if(arr[i] % j == 0) {
			primNum++;
			break;
		}
	}
	if(primNum == 0) count++;
}
System.out.println(count);

최종 풀이

실제 풀이 시간 : 28분(첫 풀이 포함)

• 입력
  • N 입력받기
  • N개의 수인 arr 입력받기
• 계산
  • 1과 자기 자신만을 약수로 가지는 수인 “소수”인 수만 저장하기
    • arr[i] == 1인 경우 → 1은 소수에서 제외시키기 위해 continue
    • 배열의 2번째 수부터 끝까지 소수인지 여부를 판별
      • primNum이 0이라면 → 이는 소수, 0이 아닌 더 큰 수라면 → 소수가 아닌 수를 뜻함.
• 출력
  • 소수 개수인 count 출력하기

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] arr = new int[N];
		int count = 0;
		
		for(int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		for(int i=0; i<N; i++) {
			if(arr[i] == 1) continue; //1은 소수에서 제외시키기
			
			int primNum = 0;
			
			for(int j=2; j<arr[i]; j++) {
				if(arr[i] % j == 0) {
					primNum++;
					break;
				}
			}
			if(primNum == 0) count++;
		}
		System.out.println(count);
	}
}