백준 1978번 자바 소수 찾기 [수학2]

단계별 문제풀기 드디어 기본 수학2에 들어왔다.

첫 번째 문제는 매너 있게 쉬운 문제다.

사실 뭐.. 지금까지들의 문제도 다 쉽긴 했다.

입력할 수 N을 입력하고 1000이하의 자연수를 네 개 입력한다.

 

입력한 수들 중 소수를 찾는 프로그램을 작성한다.

 

소수란 3.141592.. 이런게 아니라 1보다 큰 자연수 중 1과 자신의 수를 약수로 가지는 수다.

 

즉 1, 자신의 수 빼고 나눠지는 수가 있으면 안된다. ex) 1, 2, 3, 5, 7 ....

 

방법 1. 

뭐 아아주 단순하게 생각하면 입력한 수를 for문 돌려서 나눠 떨어지면 소수가 아닌것으로 검사하면 된다.

 

7이라 했을때 1 과 7은 검사대상 제외이므로 7을 2~6까지 계속 나눠보고 나눠 떨어지면 소수가 아니고 나눠떨어지는 수가 끝까지 안나오면 소수인 것으로 판별하면 된다.

 

그러나 그런 단순한 알고리즘을 짜면 좀 가오가 떨어지므로 효율적인(있어보이는) 알고리즘을 짜보자.

방법 2. 

먼저 입력값을 K라고 봤을 때 K/2 까지만 검사를 하면 된다.

 

12의 약수는 1, 2, 3, 4, 6, 12 여기서 2부터 검사하므로 2에서 나눠져서 소수가 아닌게 판별난다.

 

2의 짝궁은 6, 3은 4 즉 12를 2부터 11까지 차례로 나눠서 검사를 하면 중복검사가 일어나게 되는 것이다.

 

그래서 뭐 12나누기 2~6 까지 하면 된다. 이미 뭐 2에서 걸러지지만..

 

다른 수들도 마찬가지로 13이면 13나누기 2부터 6까지 검사해서 나눠 떨어지지 않으면 소수인 것이다.

(나머지는 무시한다) 

방법 3. 

더 효율적인 방법으로는 제곱근을 이용한다.

 

K가 소수이기 위해서는 K의 제곱근보다 크지 않는 어떤 수로도 나눠지지 않는 것 이다.

 

즉 2부터 K의 제곱근 까지로 검사하는 범위가 더 줄었다. ex) K=23 ... 23의 제곱근은 4.xxx 이므로 23을 2, 3, 4로 나눠보고 나눠지지 않으면 소수이다.

 

이제 코드로

import java.util.Scanner;
 
public class Main {
    //baekjoon 1978 소수찾기 수학2
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //수의 개수
        int cnt = 0; //소수 카운트
        
        for(int i=0; i<n; i++) { //n만큼 반복
            int k = sc.nextInt();
            boolean isPrime = true;
            
            if(k == 1)
                continue; //1은 소수가 아니므로 넘어간다.
            for(int j=2; j<=Math.sqrt(k); j++) { //Math.sqrt() 함수는 제곱근을 구하는 함수이다.
                if(k % j == 0) {
                    isPrime = false;    //k를 j로 나눠서 나눠떨어지면 소수가 아니다.
                }
            }
            if(isPrime) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
 
}
 

이번 글 역시 아주 아주 쉬운 내용을 개떡같이 설명한 것 같다.

 

별수 있나....