백준 1978 소수 찾기(Java)

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

---

bufferedreader + while 반복문도 있는데

내 스타일은 그래도 왠지 스캐너라 이번에는 스캐너로 풀어보았다.

 

1은 예제를 보니 소수가 아닌것으로 판별하여 continue 처리하였다.

2부터 제시된 수까지 끝까지 반복하면서 나누어도 되지만, 반복 횟수를 줄일 수 있는 방법이 있다.

ex ) 4의 약수는 1,2,4

6의 약수는 1,2,3,6

8의 약수는 1,2,4,8

9의 약수는 1,3,9

12의 약수는 1,2,3,4,6,12

...

: 약수를 구할 때 구하려는 수의 제곱근 까지만 반복을 돌려도 충분하다.

왜?라고 묻는다면

제곱근을 기준으로 좌우측 약수들이 대칭으로 곱해져야 정수가 된다.

또한, 소수는 2 이상 해당 정수 이하에 약수가 하나라도 존재하면 안 되니까.

제곱근보다 큰 약수는 원래 수 / 다른 약수 해서 나오는 값이다.

이를 통해 시간 복잡도를 O(n) -> O(n^(1/2)) 로 줄일 수 있다.

똑같은 생김새의 코드여도 이 편이 전체 반복 돌리는 것보다 효율이 좋다.

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        int cnt = 0;

        for(int i = 0; i < tc ; i++){
            int x = sc.nextInt();
            boolean prime = true;

            if (x == 1){    //1은 소수가 아님
                continue;
            }

            for(int j = 2; j <= Math.sqrt(x); j++){
                if(x % j == 0){    //소수가 아닌 경우
                    prime = false;
                    break;
                }
            }

            if(prime){
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}