[Do It! 코딩테스트 자바편(김종관)] 문제 038(백준: 1456번)

난이도

• 10^14이라는 큰 수를 충분히 고려해서 짜야하는 문제… 이를 고려하지 않으면 여러 오류가 나온다. 기본적으로 값의 범위를 벗어난다던지, 메모리를 초과한다던지.
• 실제로 내가 처음 코드를 짰을 때 로직은 아무리 생각해도 맞는데 왜 답이 틀린지 곰곰이 생각하다가 다음과 같은 추측에 도달했다. long형으로 변수를 선언해도, 값을 곱할 때 long형의 범위를 벗어나서 오버플로우가 발생하지 않았을지라는 추측이다. 물론 이건 내 추측이고, 확실하지 않다.

문제

거의 소수 구하기(백준: 1456번)

맞는 풀이

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long min = sc.nextLong();
        long max = sc.nextLong();
        long[] nums = new long[10000000 + 1];

        for (int i = 2; i < nums.length; i++)
            nums[i] = i;

        for (int i = 2; i <= Math.sqrt(nums.length); i++) {
            if (nums[i] == 0)
                continue;
            for (int j = 2 * i; j < nums.length; j += i) {
                nums[j] = 0;
            }
        }

        int cnt = 0;
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] == 0)
                continue;

            long temp = nums[i];
            while ((double) nums[i] <= (double) max / (double) temp) {
                if ((double) nums[i] >= (double) min / (double) temp)
                    cnt++;
                temp = temp * nums[i];
            }

        }
        System.out.println(cnt);
        sc.close();
    }
}

처음 시도한 틀린 풀이

• 문제점 성찰
  • long[] primeNum = new long[(int) max + 1]; max는 최대 10^14을 받을 수 있고, 10^14 크기의 배열을 만들면 메모리 초과한다는 에러가 뜸
  • long nearPrime = (long) Math.pow(primeNum[i], j); Math.pow(primeNum[i], j)이 long형의 범위를 넘는 사례는 바로 안 떠오른다. 하지만 교재에서는 이렇게 하지 않고, 다르게 풀었다. 따라서 이 또한 문제되는 부분일 수도 있다는 추측을 해본다. 아마 이 부분이 오버플로우와 연관이 있을 수도 있다. 단 이건 확실하지 않은 내 추측일 뿐이다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long min = sc.nextLong();
        long max = sc.nextLong();
        long[] primeNum = new long[(int) max + 1];

        for (int i = 2; i <= max; i++)
            primeNum[i] = i;

        for (int i = 2; i <= Math.sqrt(max); i++) {
            if (primeNum[i] == 0)
                continue;
            for (int j = 2 * i; j <= max; j += i) {
                primeNum[j] = 0;
            }
        }

        int cnt = 0;
        for (int i = 2; i <= max; i++) {
            if (primeNum[i] == 0)
                continue;
            for (int j = 2;; j++) {
                long nearPrime = (long) Math.pow(primeNum[i], j);
                if (nearPrime < min || nearPrime > max)
                    break;
                cnt++;
            }
        }
        System.out.println(cnt);
        sc.close();
    }
}