1978 소수 찾기 JAVA

이번 문제는 매우 간단하다.

 

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

 

우선 나는 소수를 구하기 위해서 가장 먼저 생각한 방법은 순회하며 나머지가 0이 나온다면 소수가 아닌 방식으로 판단하는거였다.

이번 문제는 제한 시간이 충분히 주어져서 문제를 푸는덴 솔직히 상관은 없지만 뭔가 내키지 않은 방식이란걸 여러분도 느꼈을 것이다.

 

 우선 소수란, 다들 알겠지만 약수로 1과 자신만을 가지는 수이다. 따라서 그 수는 이들 이외의 수를 약수로 가지면, 소수가 아닌 것이다. 

이 특징을 이용하면 되는데, 예를 들어 수가 10인 경우, 굳이 2~10 전체를 나눠가면서 나머지를 구할 필요없이, 올 수 있는 약수의 범위인

2~5만 나누면 되지 않을까? 왜냐하면 해당 수가 가질 수 있는 최대 약수의 범위는 (수/2)이기 때문이다. 그 특징을 이용하면 조금은 더 효율적인 알고리즘이 가능하지만, 뭔가 아쉬운 느낌이 났다.

 

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

public class M1978 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int cnt = 0;

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        while(N --> 0) {
            int num = Integer.parseInt(st.nextToken());

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

    private static boolean prime(int num) {
        if(num < 2) return false;

        for(int i = 2; i <= num / 2; i++) {
            if(num % i == 0)
                return false;
        }

        return true;
    }
}