[java] 백준 1456번 문제(거의 소수)

원본 링크 : https://www.acmicpc.net/problem/1456

---

문제설명

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Boj_1456
{
    public static void main(String[] args) throws IOException
    {
        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());

        int max = (int)Math.sqrt(b) + 1;
        boolean[] isPrime = new boolean[max];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for(int i = 2; i * i < max; i++)
            if(isPrime[i])
                for(int j = i * i; j < max; j += i)
                    isPrime[j] = false;

        int count = 0;
        for (int i = 2; i < max; ++i)
        {
            if (!isPrime[i]) continue;
            long value = (long) i * i;
            while (value <= b)
            {
                if (value >= a) ++count;
                if (value > b / i) break;
                value *= i;
            }
        }


        System.out.print(count);
    }
}

 

설명

• A ≤ p^k ≤ B(p는 소수, k >= 2)를 만족하는 수를 찾는 문제
• A와 B가 10^14(=100,000,000,000,000)이기 때문에 long으로 처리해야한다.
• 에라토스테네스의 체를 사용하지만, 진짜 소수를 찾는 것이 아니므로 배열의 숫자가 int 범위를 초과할 필요가 없다.

 

 

"N까지 소수를 구해야 한다면, boolean[N + 1] 크기의 배열을 만들어야 하는 것 아닌가요?"
"근데 어떻게 √N + 1만큼의 배열만 선언하고도 소수를 구할 수 있는 거죠?"

이 말이 맞는 경우도 있고, 아닌 경우도 있다.

진짜 소수 전체가 필요한지, 아니면 일부 소수만 필요한지"에 따라 달라진다.

 

우리가 찾는 건 거의 소수다. 즉, 어떤 수 p^k (단, k ≥ 2)가 주어진 범위 A ~ B에 있는지를 찾는 것이다.

그럼 여기서 중요한 점

• p^k <= B일 때 가능한 p의 최대값은?
• 이걸 k=2일 때 기준으로 보면, → p^2 ≤ B → p ≤ √B

즉, 어떤 소수 p에 대해서 p^2부터 계산할 거니까, p는 최대 √B까지만 보면 되는 것이다.

지수가 커질수록 밑은 작아져야 함
p^2 ≤ B일 때 → p ≤ √B
p^3 ≤ B일 때 → p ≤ B^(1/3)
p^4 ≤ B일 때 → p ≤ B^(1/4)
...

즉, k가 커지면 커질수록 p는 점점 더 작아져야 한다.
→ 그러니까 p가 클 수 있는 한계는 k = 2일 때뿐이다.
→ 그때 가장 큰 p가 √B인 것이다.

때문에 아래처럼 작성해도 된다.

int max = (int)Math.sqrt(b);
boolean[] isPrime = new boolean[max + 1];

 

그 다음으로 문제가 되는 부분은 아래의 코드이다.

int count = 0;
for(int i = 2; i < max; ++i)
{
    for(int j = 2; j < 100; ++j)
    {
	double pow = Math.pow(i, j);
        if (pow > b) break;
        if (isPrime[i] && pow >= a) ++count;    
    }

}

이 코드는 내가 처음에 작성한 코드인데 문제를 맞추는데는 전혀 문제없지만, j의 범위를 그냥 무작정 크게한 것이 마음에 걸렸다.

그리고 Math.pow()는 double을 반환하기 때문에 정확한 정수값이 아닐 수 있다. (부동소수점 오차)

그래서 아래와 같이 바꿨다.

int count = 0;
for (int i = 2; i < max; ++i)
{
    if (!isPrime[i]) continue;
    long value = (long) i * i;
    while (value <= b)
    {
        if (value >= a) ++count;
        if (value > b / i) break; // 오버플로우 방지
        value *= i;
    }
}

오버플로우 방지
우리가 실제로 확인하고 싶은 것은 value * i > b 이다.
하지만 이렇게 직접 곱하면 오버플로우가 발생할 수 있다.

그래서 식을 변형한 것이다.
value * i > b
value > b / i