[Java] 백준 1978번 : 소수 찾기

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

1978번: 소수 찾기

 

교내 SW개발 경진 대회에서 연소수 문제에 충격 받아서 푼 소수 기초 문제

 

 

 

접근 방법

소수 구하는 알고리즘을 몰라서

if(i%!2 =0 && % !3 =0  && % !5 =0  && % !9 =0)

부끄럽지만 이렇게 작성했었다 

 

이것보다 간단한 알고리즘이 있을 것 같아서 찾아보다가 좋은 자료를 발견했다

참고 자료 : https://www.youtube.com/watch?v=CyINCmJPjfM

 

 

접근 방법

1) Math.sqrt를 이용한 소수 알고리즘

2부터 입력받은 수의 제곱근까지 나누어 떨어지는지 확인해서 소수임을 확인한다.

제곱근까지 확인하는 이유? 약수의 성질이기 때문에 제곱근(가운데 약수)까지만 확인하면 된다. 

 

2) 1은 소수에서 제외한다

if(x<2)로 2보다 작을 경우 바로 false를 반환

 

3) 공백 기준으로 숫자들 입력받는다

String[] input = br.readLine().split(" ");

 

 

정답 코드 

import java.io.*;

public class Main {
	public static boolean isPrime(int x) {
		if(x<2) // x가 1일 경우 바로 false 반환
			return false;
		for(int i=2; i<= Math.sqrt(x); i++) {
			if (x%i==0) // x가 해당 수로 나눠떨어지면 
				return false; // 소수x
		}
		return true; // x가 나누어떨어지지 않으면 소수o
	}
	
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int count = 0;
		
		int N = Integer.parseInt(br.readLine()); // 첫 줄에 수의 개수 N
		String[] input = br.readLine().split(" "); //두번째 줄에 공백 기준으로 숫자들 입력받음
		
                for (int i = 0; i < N; i++) {
                    if (isPrime(Integer.parseInt(input[i]))) { 
                        count++; // 소수인 경우 count 증가
                    }
                }

            bw.write(String.valueOf(count));
            bw.flush();
            bw.close();
	}
}