[백준 4233번] 가짜 소수 - JAVA

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

4233번: 가짜소수

풀이

사용한 알고리즘 : 분할정복, 소수 구하기

 

풀이전략

 

이 문제를 풀기위해서는 소수 구하기와 분할정복 알고리즘을 알아야한다.

 

1. 소수 구하기

먼저 소수 구하기를 구현한 isPrime 함수부터 설명을 하겠다.

static boolean isPrime(long num){
    if(num<2) return false;
    for(long i=2;i*i<=num;++i){
        if(num%i==0) return false;
    }
    return true;
}

위 함수는 주어진 수가 소수이면 true를, 소수가 아니면 false를 반환하도록 하는 함수이다.

먼저 0과 1은 소수가 아니므로 false를 반환한다.

 

중간에 반복문이 있는데 내부의 조건문을 보면 i*i<=num으로 되어있다.

이유는 2에서부터 주어진 수의 제곱근에 해당하는 수까지만 입력받은 수에 나누었을 경우,

나누어 떨어지는 수가 있는지 확인하기 위해서다.

 

만약 16이라는 수가 num으로 주어졌다고 생각해보자.

16의 약수로는 1, 2, 4, 8, 16이 있다.

1*16

2*8

4*4

8*2

16*1

따라서 16은 위와 같이 표현될 수 있는데, 16의 제곱근은 4로 중앙에 위치해 있음을 알 수 있다.

 

16을 2로 나눈 경우, 딱 나누어 떨어지면서 몫이 8이다.

이는 16을 8로 나눈 경우, 마찬가지로 딱 나누어 떨어지며 몫이 2가 되는 것과 동일하다.

 

즉, 입력받은 수를 2에서부터 주어진 수의 제곱근까지의 수로 나누어 떨어졌을 경우만 구해도

모든 약수를 찾아 나눈 것과 동일한 결과를 얻을 수 있다.

 

따라서 반복문 내의 조건을 i<=root(num)에서 양변에 제곱을 한 i^2 <= num으로 했다.

 

단, 우리는 소수를 구하는 것이기 때문에 나누어 떨어지는 것이 하나라도 없어야 소수로 true를 반환한다.

 

2. 분할 정복을 통한 제곱한 수 구하기

a의 p 제곱을 구한다고 생각해보자.

쉽게 생각해보면 반복문을 통해 a를 p번 곱하면 가능할 것이다.

하지만 문제에서는 p의 범위가 2<=p<=1,000,000,000 라고 주어졌다.

그러면 최약의 경우 제곱한 수를 구하기 위해 1,000,000,000번의 연산이 필요하게 된다.

 

보통 알고리즘 테스트에서 JAVA는 1초에 1억번의 연산을 할 수 있다고 한다.

그런데 최대로 그보다 10배 많은 10억이 주어지면 시간 제한인 1초를 넘어선 10초가 걸리게 된다.

 

따라서 O(N)을 탈피한 다른 방법의 제곱수 구하는 방법을 사용해야한다.

static long fpow(long a, long p, long mod){
    if(p==1){
        return a;
    }
    else{
        long x = fpow(a,(long)(p/2),mod);

        if((p%2)==0){
            return (x*x)%mod;
        }
        else{
            return (((x*x)%mod)*a)%mod;
        }
    }
}

제곱으로 들어가는 수가 짝수인 경우와 홀수인 경우 나누어 연산을 실행한다.

 

만약 c는 2, n으로 16이 주어졌다고 생각해보자.

2^16 = 2^8 * 2^8

2^8 = 2^4 * 2^4

2^4 = 2^2 * 2^2

2^2 = 2^1 * 2^2

2^1 = 2

 

로 원래 16번 연산을 시행해야 하던 것이, log16+1번 시행된다.

즉 시간 복잡도를 O(N)에서 O(logN)으로 줄일 수 있는 것이다.

 

위의 소수 구하기와 분할 정복을 통한 제곱한 수 구하기 알고리즘을 사용하면 아래와 같이

문제풀이가 가능하다.

 

제출코드

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

public class Main {
    static boolean isPrime(long num){
        if(num<2) return false;
        for(long i=2;i*i<=num;++i){
            if(num%i==0) return false;
        }
        return true;
    }

    static long fpow(long a, long p, long mod){

        if(p==1){
            return a;
        }
        else{
            long x = fpow(a,(long)(p/2),mod);

            if((p%2)==0){
                return (x*x)%mod;
            }
            else{
                return (((x*x)%mod)*a)%mod;
            }
        }
    }
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        long A,B;
        long a,p;

        while(true){
            st = new StringTokenizer(br.readLine());
            A = Long.parseLong(st.nextToken());
            B = Long.parseLong(st.nextToken());

            if(A==0 && B==0) break;

            a = Math.min(A,B);
            p = Math.max(A,B);

            if(isPrime(p)){
                bw.write("no\n");
            }
            else{
                if(fpow(a,p,p)==a) bw.write("yes\n");
                else bw.write("no\n");
            }

        }
        bw.flush();
        bw.close();
    }
}