[자바 JAVA/알고리즘] 백준 1978번 : 소수 찾기

//GitHub https://github.com/vellimole0621

vellimole0621 - Overview

백준 1978번 : 소수 찾기

 

(문제 - https://www.acmicpc.net/problem/1978)

 

문제 설명 : 숫자 N를 받아, N개 만큼의 숫자를 입력받는다. 그 숫자들 중에 소수 개수를 출력하라.

 

풀이 : N를 입력받음 >> 반복문 조건에 사용될 변수들 초기화 >> N개 만큼 자연수 입력 받고, 1부터 자기 자신 -1 까지 나머지 없이 나누어지는 경우 검사 >> 수가 1이 아니고 나누어 지는 경우가 하나 밖에 없으면 소수로 판단 >> 소수 개수 출력

 

// 1978번 소수 찾기

package S2208;
import java.util.*;

public class Main {
 public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    // N 입력 받기
    int N = sc.nextInt();

    // 반복문 조건에 사용될 변수들 초기화
    int res = 0;
    int b = 1;
    int c = 0;
    int a = 0;

	// N개 만큼 자연수 입력 받기
    for(int i = 0; i < N; i++){
        a = sc.nextInt();
        // 1 부터 a-1 까지 나눠서, 나머지 없이 나누어지는 경우 확인
        while(b != a){
            if(a%b==0){
                c++;
            }
            b++;
        }
        b = 1;

        // 입력이 1이 아닐 때, 나머지 없이 나누어지는 경우 소수라 판별
        if(a != 1){
            if(c == 1){
                res++;
            }
        }
        c = 0;
    }

    // 소수 개수 출력
    System.out.println(res);

    sc.close();

 }   
}

어려웠던 점 : 소수를 찾기 위해, 나눗셈을 반복할 때. for 문을 사용하면 시간이 너무 오래 걸렸다. 그래서, while 사용해 입력 받은 수 -1 까지 반복되게 하여서, 반복 횟수를 줄였다.