728x90
반응형
SMALL
문제 링크
https://www.acmicpc.net/problem/1978
문제 설명
주어진 수 N개 중에서 소수가 몇 개인지 찾는 프로그램을 작성하는 문제입니다.
입력
- 첫 번째 줄에 자연수 N이 주어집니다. (1 ≤ N ≤ 100)
- 두 번째 줄에 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; // 소수임
}
}
배운점
조금씩 따로 기능에 따른 메서드를 나눠서 알고리즘에 대입하는것을 연습해볼 수 있었다.
여러 라이브러리를 알고리즘 공부를 통해 기억해서 그 기능을 기억하자
소수 찾기는 정말 기본적인 코딩테스트에 자주 나오는 문제이니 이해가 가지 않는다면 외워두는것도 좋을듯 싶다!
728x90
반응형
LIST
'코딩테스트' 카테고리의 다른 글
[코딩테스트] programmers - 같은 숫자는 싫어 (알고리즘 고득점 kit) [JAVA] (0) | 2025.03.11 |
---|---|
[코딩테스트] programmers - 완주하지 못한 선수(알고리즘 고득점 kit) [JAVA] (1) | 2025.02.02 |
[코딩테스트] programmers - 네트워크 (알고리즘 고득점 kit) [JAVA] (1) | 2025.02.02 |
[코딩테스트] programmers - 타겟넘버 (알고리즘 고득점 kit) [JAVA] (1) | 2025.01.25 |
[코딩테스트] programmers - 폰켓몬 (알고리즘 고득점 kit) [JAVA] (1) | 2025.01.13 |