[java] 백준 알고리즘 1978번 소수 찾기 풀이

소수가 아닌 경우를 탈락 시켜 나가면서 해결했다.

이 공식을 활용했다.

수가 수를 나누기 위해서는 그 몫이 항상 필요하며 나누는 수와 몫 중 어느 하나는 반드시 ${\displaystyle {\sqrt {n}}}$ 이하이기 때문이다.  - 출처: 위키피디아

while문에서 나누는 수가 제곱근 이상이 되면 break를 걸었다.

* 풀이 소스 

public class Baekjoon1978{
 
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int primeNumCount = N;
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            int primeNumber = Integer.parseInt(st.nextToken());
            int squareRoot  = (int) Math.sqrt(primeNumber);
            int divide = 2;
            
            if(primeNumber > 1) {
                
                while(squareRoot >= divide) {
                    
                    if(primeNumber%divide == 0) {
                        primeNumCount--;
                        break;
                    }
                    divide++;
                }
            }else { // 1이 입력될 경우 1은 소수가 아님
                primeNumCount--;
            }
            
        }
        bw.write(String.valueOf(primeNumCount));
        bw.flush();
        
    }
 
}