[자바] 백준 1456 - 거의 소수 (java)

 문제 : boj1456

---

 

필요 알고리즘 개념

•  소수 판정, 에라토스테네스의 체
  • 범위 내의 모든 소수를 찾아야 하므로 소수 판정, 더 나아가 에라토스테네스의 체를 알아야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  어떤 수가 소수의 N제곱(N>=2) 꼴일 때를 찾아줘야 한다. 이 때 오른쪽 범위 B가 10^14이고 N>=2 이므로 최대 10^7까지의(sqrt(B) 까지 알아야 한다) 모든 소수를 찾아야 함을 알 수 있다. 주의점은 A값은 소수를 찾을 때 의미가 없다. 어차피 소수의 N제곱꼴이 필요한 것이므로, A가 값이 크다고 더 적게 찾아야 하는건 아니다. B에만 영향을 받는다.

 

  만약 범위내의 모든 소수 리스트를 알고 있다면 소수 리스트를 순회하면서 하나씩 B까지 N제곱을 해보면서 A에서 B 사이에 걸리면 카운팅해주면 된다.

 

  예를들어 A=5, B=16 이라 해보자. 이 때 알아야 하는 소수는 sqrt(16) = 4 이하의 모든 소수이다. 그럼 2와 3이 존재한다.

소수 2부터 보자. B이내에 2의 N제곱은 2^2 = 4, 2^3 = 8, 2^4 = 16 이고, 이 때 [A, B]범위 내에 8과 16이 있으므로 2개 카운팅 해준다.

소수 3에 대해 3의 N제곱은 B이내에  3^2 = 9만 존재하고, 이 값이 [A, B] 범위내에 포함되므로 1개 카운팅 해준다.

최종적으로 3이 답이 된다.

 

  그럼 로직별로 어떻게 푸는지 살펴보자.

 

1. sqrt(B) 이하의 모든 소수를 찾아보자.

  이건 에라토스테네스의 체 알고리즘을 써주면 모두 구해 리스트화 시킬 수 있다. 이 때, 에라토스테네스의 체는 구하려는 소수 리밋의 제곱근 까지만 보면 된다. 이건 '에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유' 글에서 확인해보자. 에라토스테네스의 체로 소수 구하는 법을 모른다면 검색해서 꼭 개념을 익혀두자. 알고리즘에서 엄청 자주 쓰인다.

private ArrayList<Integer> getPn(int LIMIT) {
    ArrayList<Integer> pn = new ArrayList<>();
    boolean[] isPn = new boolean[LIMIT+1];
    int sqrtN = (int)Math.sqrt(LIMIT);
    for (int i = 3; i <= sqrtN; i+=2) {
        if (isPn[i]) continue;
        int base = i+i;
        while (base <= LIMIT) {
            isPn[base] = true;
            base+=i;
        }
    }
    pn.add(2);
    for (int i = 3; i <= LIMIT; i+=2) {
        if (!isPn[i]) pn.add(i);
    }
    return pn;
}

 

---

 

2. '1'에서 구한 소수 리스트를 순회하면서 소수의 N제곱을 찾자.

  이건 그냥 B 이하 모든 값에 대해 전부 봐주면 된다.

for (int i = 0; i < pn.size(); i++) {
    long cur = pn.get(i);
    int curCnt = getLength(cur);
    long tmp = cur;
    while ((tmp*=cur)<=b) {
        if (a<=tmp)
            cnt++;
        int tmpCnt = getLength(tmp);
        if (curCnt + tmpCnt > 15)
            break;
    }
}

 

 

  다만 이 문제가 그냥 이것만 필요했다면 실버1까지 안갔다. 이 문제의 경우 long으로 표현해도 오버플로우의 위험이 있다. 예를들어 A=1, B=10^14인 경우 '1'에서 찾아지는 가장 큰 소수는 '9999991' 이고, 이걸 X라고 하겠다. 그럼 X^2을 우선 보겠고, 그건 10^14이며, 그건 B값보다 작다. 따라서 한번 더 X^3을 보게될 수 있는데 그럼 long으로 해도 오버플로우가 발생한다(대강 10^21이 되버린다.).

 

  따라서 오버플로우가 나지 않도록 해줘야 한다. 내 경우엔 X의 길이를 미리 구해두고, X^N의 자리수를 매번 구해서 만약 한번 더 곱했을 때(즉 두 자리수를 합한 값이) 10^15를 넘어가게 된다면 그냥 곱해보지 않는 식으로 처리했다. 코드로는 아래의 부분이 그 역할을 한다.

if (curCnt + tmpCnt > 15)
	break;

 

---

코드 : github

ㅇimport java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private ArrayList<Integer> getPn(int LIMIT) {
        ArrayList<Integer> pn = new ArrayList<>();
        boolean[] isPn = new boolean[LIMIT+1];
        int sqrtN = (int)Math.sqrt(LIMIT);
        for (int i = 3; i <= sqrtN; i+=2) {
            if (isPn[i]) continue;
            int base = i+i;
            while (base <= LIMIT) {
                isPn[base] = true;
                base+=i;
            }
        }
        pn.add(2);
        for (int i = 3; i <= LIMIT; i+=2) {
            if (!isPn[i]) pn.add(i);
        }
        return pn;
    }

    private int getLength(long num) {
        int cnt = 0;
        while (num!=0) {
            cnt++;
            num/=10;
        }
        return cnt;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        ArrayList<Integer> pn = getPn((int)Math.sqrt(b));
        int cnt = 0;
        for (int i = 0; i < pn.size(); i++) {
            long cur = pn.get(i);
            int curCnt = getLength(cur);
            long tmp = cur;
            while ((tmp*=cur)<=b) {
                if (a<=tmp)
                    cnt++;
                int tmpCnt = getLength(tmp);
                if (curCnt + tmpCnt > 15)
                    break;
            }
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}