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

2025. 1. 6. 01:05·코딩테스트
728x90
반응형
SMALL

문제 링크

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; // 소수임
	}
}

배운점

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

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

 


 

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

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
'코딩테스트' 카테고리의 다른 글
  • [코딩테스트] programmers - 완주하지 못한 선수(알고리즘 고득점 kit) [JAVA]
  • [코딩테스트] programmers - 네트워크 (알고리즘 고득점 kit) [JAVA]
  • [코딩테스트] programmers - 타겟넘버 (알고리즘 고득점 kit) [JAVA]
  • [코딩테스트] programmers - 폰켓몬 (알고리즘 고득점 kit) [JAVA]
junhyeokkk
junhyeokkk
나의 개발자 성장기
  • junhyeokkk
    백엔드 개발자 준혁의 성장일지
    junhyeokkk
  • 전체
    오늘
    어제
    • 분류 전체보기 (59)
      • Flutter (13)
      • 개발환경구축 (3)
      • HTTP (0)
      • CS지식 (5)
      • 코딩테스트 (10)
      • JAVA (7)
      • 데이터베이스 (7)
      • Node.js (9)
      • TypeScript (1)
      • Azure (3)
      • Git (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
    • 글쓰기
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    백엔드개발자
    코딩테스트
    디자인패턴
    db
    데이터베이스
    DART
    node
    Flutter
    azure
    Java
    sql튜토리얼
    개발자준비
    알고리즘
    백엔드개발
    CS지식
    백엔드
    개발자
    js
    cosmos db
    Typescript
    RDBMS
    node.js
    Microsoft
    programmers
    자바
    nodejs
    마이크로소프트sql
    MSsql
    라이브러리
    프로그래머스
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
junhyeokkk
[코딩테스트] 백준 1978 - 소수 찾기 [JAVA]
상단으로

티스토리툴바