[문제 풀이] 백준 1978번 소수 찾기 JAVA

문제

 

백준 1978번은 주어진 수 N개 중에서 소수가 몇 개 인지 찾아서 출력하는 프로그램을 작성하는 문제이다.

해당 문제를 보고 접근한 방식은 시간 제한이 2 초고 범위가 100 이하이기 때문에

이중 for문을 사용하여도 시간 제한이 큰 문제가 되지 않을 것으로 판단하여 아래와 같이 접근해 보았다.

 

소수의 조건이 본인과 1을 제외한 약수가 없어야 하는 것이므로

입력받은 숫자 num [i]를 1~num [i]까지의 숫자로 나누고

나머지가 0일 때를 카운트해서 카운트 값이 2가 넘으면 소수로 체크하는 방식을 사용하였다.

예를 들어서 1 3 5 7을 입력받았다면 1~1, 1~3,1~5,1~7로 각각의 숫자를 나누고

약수가 몇 개인지 판단해서 소수인지 아닌지를 결정하는 것이다.

 

< 소수 기본 판별법 1 >

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int num[]=new int[n];
        for(int i=0;i<n;i++){
            num[i]=s.nextInt();
        }
        System.out.print(decimal(num));
    }
    public static int decimal(int num[]){
        int cnt=0;
        
        for(int i=0;i<num.length;i++){
            int count=0;
            for(int j=1;j<num[i]+1;j++){
                if(num[i]%j==0)count++;
            }
            if(count==2)cnt++;
        }
        return cnt;
        
    }
}

본 코드는 시간 복잡도가 O(nM)이지만 무조건 1~num [i]까지 연산을 해야 하므로 불필요한 연산이 존재하게 된다.

아래 코드는 불필요한 연산을 줄이는 방식으로 구성해 보았다.

 

< 소수 기본 판별법 ver 개선 >

import java.util.*;

//기본 판별법
public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int cnt=0;
        int num[]=new int[n];
        for(int i=0;i<n;i++){
            num[i]=s.nextInt();
            if(decimal(num[i])){cnt++;}
        }
        System.out.println(cnt);
    }
    public static boolean decimal(int num){
        if(num==1) return false;
        for(int i=2;i<num;i++){
            if(num%i==0) return false; // 소수는 1과 자신을 제외한 약수가 존재하면 안된다.
        }
        return true;
        
    }
}

해당 코드는 처음 코드와 같은 시간 복잡도인 O(nM)를 가져 별다를 게 없어 보이지만

소수를 구하는 연산중에 false를 반환하여 불필요한 연산을 줄일 수가 있다는 차이를 가지고 있다.

 

위의 방식을 제외하고도 소수를 판별하는 방법은 여러 가지가 존재한다. 

본 글에서는 간단하게 언급만 하고 넘어가겠다.

 

먼저 위에서 사용한 

1. 소수 기본 판별법

2. 제곱근까지만 확인하는 방법

3. 6의 배수 최적화

4. 에라토스테네스의 체

5. 밀러-라빈 소수 판별법

6. 휠 소거법

 

자세한 내용은 아래 링크를 통해 확인해 볼 수 있다.

https://hmkang32180116.tistory.com/15

[알고리즘] 소수 판별법

 

 

위에서 소개한 판별법 둘 중 몇 가지를 코드로 구현해 보았다.

 

< 제곱근까지만 확인하는 방법 >

소수는 자신의 제곱근 이하의 수 중에서만 나누어 떨어지는지 확인하면 되는 것을 이용한 방법이다.

import java.util.*;

//제곱근을 이용한 방법
public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int cnt=0;
        int num[]=new int[n];
        for(int i=0;i<n;i++){
            num[i]=s.nextInt();
            if(decimal(num[i])){cnt++;}
        }
        System.out.println(cnt);
    }
    public static boolean decimal(int num){
        if(num==1) return false;
        for(int i=2;i*i<=num;i++){
            if(num%i==0) return false; 
        }
        return true;
        
    }
}

본 코드는 제곱근까지만 확인하여 시간복잡도가 O(n√M)되며 O(nM)의 시간복잡도를 가지는

기본 판별법보다 훨씬 빠른 알고리즘이다.

 

< 6의 배수 최적화 >

모든 소수는 6의 배수 ±1 형태를 따르는 성질이 있다.

2와 3을 제외한 모든 소수는 6으로 나눈 나머지가 1 또는 5이다.

따라서 2와 3을 먼저 판별 후, 6의 배수 ±1인 숫자만 검사하면 더 빠르게 확인할 수 있는 것이다.

import java.util.*;

//6의 제곱근을 이용한 방법
public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int cnt=0;
        int num[]=new int[n];
        for(int i=0;i<n;i++){
            num[i]=s.nextInt();
            if(decimal(num[i])){cnt++;}
        }
        System.out.println(cnt);
    }
    public static boolean decimal(int num){
        if(num==1) return false;
        if(num==2||num==3) return true;
        if(num%2==0||num%3==0) return false;
        for(int i=5;i*i<num;i++){
            if(num%i==0||num%(i+2)==0) return false; 
        }
        return true;
        
    }
}

if(num% i==0||num%(i+2)==0) return false;  해당 식은 처음에는 이해가 가지 않았는데

위에서부터 코드를 쭉 실행해서 내려오면  1,2,3,4가 제외되고 2의 배수 , 3의 배수도 제외되기 때문에 

검사해야 할 수 들은 5,7,11,13,17,19,23,25,29,31..... 등이 존재하게 되는데 6의 배수 ±1인 형태를 확인할 수 있다.

i는 6의 배수 -1의 형태 i+2는 6의 배수 +1의 숫자가 된다. 

위의 코드는 O(n√M)의 시간복잡도를 가지지만 6의 배수 ±1인 숫자만 검사하여 연산을 줄이게 되는데 

이는 실제 실행속도가 더 빨라지는데 도움을 준다.

 

마지막으로 소수를 구하는데 있어서 특정 상황을 제외하고는 가장 빠르다고 평가 받는 에라토스테네스의 체 방식으로

문제를 풀이해보겠다.

< 에라토스테네스의 체 >

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
    
        int n=s.nextInt();
        boolean[] prime=new boolean[1001];
        Arrays.fill(prime,true);
        prime[0]=prime[1]=false;

        primeTools(prime);
        int cnt=0;
        for(int i=0;i<n;i++){
            int num=s.nextInt();
            if(prime[num]){cnt++;}
        }
        System.out.println(cnt);
    }
    public static void primeTools(boolean prime[]){
        for(int i=2;i<prime.length;i++){
            if(prime[i]){
                for(int j=i*i;j<prime.length;j+=i){
                    prime[j]=false;
                }
            }
            
        }
    }
   
}

에라토스테네스의 체 알고리즘의 기본 원리는 소수를 구하고자 하는  범위만큼의 크기의 배열을 만들고

배열에 소수이면 true 소수가 아니면 false로 구분해 저장한다. 그 후 소수판별을 하고자하는 숫자를 배열 index에 넣어주면

소수라면 true 소수가 아니면 false로 나타나 소수를 판별할수 있는 것이다.

여기서 핵심은 true/false를 저장하는 방식인데 에라스토테네스의 원리는 아래와 같다.

1. 소수를 판별하고자 하는 범위+1크기를 가진 배열을 생성한다.
2. 배열을 true로 채워주고 소수가 아닌 배열[0] 과 배열[1]을 false로 저장해준다.
3. 이후 2부터 반복문을 진행하는데 0과 1을 제외한 경우 2는 당연히 소수이다.
4. 2의 배수는 모두 소수가 아니기 때문에 false로 저장한다.
5. 이후 조건문에서 false라면 소수가 아니기때문에 다음으로 넘어가고 true라면 소수이기 때문에 조건문안에 반복문을 반복한다.
6. 이 과정을 계속 반복하다보면 2 3 5 7 이런식으로 소수인 숫자들만 if조건문에 충족해 소수의 배수들을 모두 false처리해 주는 것이 가능하다.
7. 과정이 끝나면 배열에는 소수인 경우에만 true이기때문에 이 부분을 활용해 원하는 숫자의 소수 판별이 가능해진다.