[코딩테스트] 백준 1978 - 소수 찾기 [JAVA]

문제 링크

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

 

 

문제 설명

주어진 수 N개 중에서 소수가 몇 개인지 찾는 프로그램을 작성하는 문제입니다.

 

입력

1. 첫 번째 줄에 자연수 N이 주어집니다. (1 ≤ N ≤ 100)
2. 두 번째 줄에 N개의 자연수가 공백으로 구분되어 주어집니다. (1 ≤ 각 수 ≤ 1,000)

출력

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

---

예제 입력과 출력

예제 입력

 

예제 출력

 

• 풀이
  • 입력된 수 중에서 1은 소수가 아니며, 3, 5, 7은 소수이므로 총 3개의 소수가 있습니다.

---

소수 판별 알고리즘

• 소수란 1과 자기 자신만으로 나누어떨어지는 수를 말합니다.
• 소수 판별을 위해 효율적인 방법으로 제곱근을 활용했습니다.
  • 어떤 수 n의 약수는 √n 이하에서만 확인하면 충분합니다.
  • 즉, 2부터 √n까지의 수 중에서 나누어떨어지는 수가 하나라도 있으면 소수가 아닙니다.

---

Java 코드

아래는 문제를 해결하기 위한 Java 코드입니다.

package codingtest;

import java.util.Scanner;

// 소수 찾기 
public class Backjoon1978 {
	
	public static void main(String args[]) {
		
		Scanner sc = new Scanner(System.in);
		int result = 0;
		int num = sc.nextInt();
		
		for(int i=0; i<num; i++) {
			int a = sc.nextInt();
			result += isPrime(a);
		}
		
		System.out.println(result);
	}
	
	// 소수찾기 메서드 외워버리기 
	public static int isPrime(int n) {
		if(n <= 1) {
			return 0;
		}
		
		for (int i = 2; i <= Math.sqrt(n); i++) {
	        if (n % i == 0) {
	            return 0; // 소수가 아님
	        }
	    }
	    return 1; // 소수임
	}
}

---

배운점

조금씩 따로 기능에 따른 메서드를 나눠서 알고리즘에 대입하는것을 연습해볼 수 있었다.

여러 라이브러리를 알고리즘 공부를 통해 기억해서 그 기능을 기억하자

 

---

 

소수 찾기는 정말 기본적인 코딩테스트에 자주 나오는 문제이니 이해가 가지 않는다면 외워두는것도 좋을듯 싶다!