백준 1978 소수 찾기 Java

소수 문제의 기초 문제이다.

풀이가 어렵지도 않은 문제를 다시 한번 정리하는 이유는

소수를 찾는 세 가지 방법에 대해 정리하기 위해서이다.

 

소수를 찾는 방법 중 가장 빠르다고 알려진 방법은 에라토스테네스의 체를 이용하는 방법이다.

하지만 다른 방법들 보단 복잡하기 때문에 에라토스테네스의 체는 다른 문제를 통해 

정리하기로 하고 이 문제에서는 에라토스테네스를 제외한 빠른 방법들을 정리하고자 한다.

 

가장 기본 적인 방법으로는 n이 있을때 n이 소수인지 판명하기 위해

n을 2부터 n-1까지 나눠보는 방법이 있다.

소수는 약수가 1과 자기자신 뿐이여야 하기 때문에 자신 보다 작은 어떤 수와

나누어 떨어진다면 그 수는 약수가 아니다.

 

for(int i=2; i<n; i++)

     if(n%i == 0)

          break; // 약수가 아니다.

 

하지만 위의 방법은 시간 복잡도 O(n)으로 소수를 찾는 방법중에 가장 오래걸린다.

이 문제는 풀 수 있지만 다른 문제는 풀 수 없고, 누군가 소수를 구해보라고 할 때

이 방법을 이용하기는 좀 그렇지 않을까 생각한다.

 

그 다음은 n을 2부터 n/2까지만 나누어 보는 것이다.

소수를 찾을 땐 2부터 시작하기 때문에 약수 중에 가장 큰 값은

2와 짝을 이루는 n/2일 것이다. 그러므로 굳이 n-1까지 나누어 볼 것이아니라

n/2까지만 나누어 봐도 충분히 소수인지 아닌지를 찾아낼 수 있는 것이다.

 

for(int i=2; i<=n/2; i++) // n/2까지기 때문에 <= 로 포함시켜줘야 한다.

     if(n%i == 0)

          break; // 약수가 아니다.

 

이 방법은 전에 방법보다는 빠르겠지만 여전히 O(n)이다.

 

마지막 방법은 2부터 루트n까지만 비교해보는 방법이ㅎ다.

루트n까지만 비교해봐도 소수인지 아닌지 알 수 있는 이유는

약수인 두 쌍 a, b 둘 중 하나는 무조건 루트n보다 작게 된다. 그리고

약수인 두 수 a X b 를하면 당연히 n이 나와야 한다. 하지만

둘 다 루트n 보다 크다면 두 수를 곱했을 때 절대 n이 나올 수가 없기 때문이다.

따라서 두 수 a와 b의 차이가 가장 적은 경우는 루트n이다. 

그렇기때문에 우리는 2부터 루트n까지만 비교해보아도 소수인지 아닌지 찾을 수 있는 것이다.

 

하지만 i<=루트n 을 한다면 루트n은 소수일 것이고 그렇게 되면 오차가 생기게 되기 때문에

i*i <= n 처럼 조건을 적어서 소수를 구하면 될것이다.

 

for(int i=2; i*i<=n; i++) // 루트n 까지기 때문에 <= 로 포함시켜줘야 한다.

     if(n%i == 0)

          break; // 약수가 아니다.

 

이 방법으로 구하면 시간 복잡도는 O(루트n)으로

n이 1억인 경우에 n=100000000

for문이 실행되는 횟수는

첫 번째 방법은 1억번

두 번째 방법은 n/2 5천만번

세 번째 방법은 루트n 만번을 실행하게 된다.

따라서 세번째 방법이 간단하게 소수를 찾는 방법 중에는 제일 빠른 방법이라고 볼 수 있다.

 

    public static void main(String[] args) {
        Scanner scan= new Scanner(System.in);
        int count = 0;
        int n =scan.nextInt();
 
        for(int i=0; i<n; i++) {
            int x = scan.nextInt();
            boolean b = false;
            if(x==1) //1은 소수가 아니기 때문에 continue
                continue;
            for(int j=2; j*j<=x; j++) {
                if(x%j==0) {
                    b = true;
                    break;
                }
            }
            if(!b)
                count++;
        }
        System.out.println(count);
    }