• 문제: https://www.acmicpc.net/problem/1016

설명

이 문제를 보고 에라토스테네스의 체로 풀이해야겠다고 생각했으나, 큰 수를 처리하는 부분에서 어려움이 있었다. 문제의 입력 범위가 1,000,000,000,000이므로 long 타입으로 관리해야 한다.
제곱ㄴㄴ수는 제곱수로 나누어 떨어지지 않는 수를 말한다. 따라서 min부터 max 사이의 숫자들이 제곱수로 나뉘어 떨어지는지 관리한다.

MIN = Long.valueOf(st.nextToken());
MAX = Long.valueOf(st.nextToken());

제곱ㄴㄴ수인지 관리하기 위한 boolean 형식의 numbers 배열과 나눌 숫자들을 관리할 modNumbers를 관리할 List를 생성한다. (false -> 제곱ㄴㄴ / true -> 제곱 ㄴㄴ X)

• modNumbers에 담기는 숫자들은 min부터 max 사이의 숫자들이 제곱수로 나뉘어 떨어지는지 확인하기 위한 숫자들이다. 따라서 제곱수들이 저장된다.

numbers = new boolean[(int) (MAX - MIN + 1)];
modNumbers = new ArrayList<>();

modNumbers의 숫자들을 min부터 max까지 나눈다.
예를들어 min이 30이고 max가 100이다. 첫번째 modNumber는 4일 것이다.
30 / 4 = 7.5이고 이 숫자는 4로 나뉘어 떨어지지 않는다. -> 따라서 제곱ㄴㄴ수의 0번째 인덱스는 false이다.
다음으로 31/4 = 7.xxx 이고 역시 4로 나뉘어 떨어지지 않는다. -> 제곱ㄴㄴ수의 1번째 인덱스는 false이다.
32/4 = 8, 즉 나뉘어 떨어진다. -> 제곱 ㄴㄴ의 2번째 인덱스는 true이다.

for (int i = 0; i < modNumbers.size(); i++) {
	// MIN: 30 / MAX: 100
	double t = (double) MIN / (double) modNumbers.get(i);	// 7.5
	
    // 4*8 - 30 = 2
    long start = (long) ((modNumbers.get(i) * Math.ceil(t)) - MIN);

    for (long j = start; j < numbers.length; j += modNumbers.get(i)) {
    	numbers[(int) j] = true;
    }
}

이제 남은 부분은 numbers 배열에서 제곱 ㄴㄴ인 것만 확인하여 count 변수에 더하고, 출력하면 된다.

int count = 0;

for (int i = 0; i < numbers.length; i++) {
	if (!numbers[i]) {
    	count++;
    }
}
System.out.println(count);

코드

package Algorithm.P1016;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class P1016 {
    static long MIN, MAX;
    static boolean[] numbers;
    static List<Long> modNumbers;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/Algorithm/P1016/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        MIN = Long.valueOf(st.nextToken());
        MAX = Long.valueOf(st.nextToken());
        numbers = new boolean[(int) (MAX - MIN + 1)];
        modNumbers = new ArrayList<>();

        for (long i = 2; i <= Math.sqrt(MAX); i++) {
            modNumbers.add(i * i);
        }

        for (int i = 0; i < modNumbers.size(); i++) {
            double t = (double) MIN / (double) modNumbers.get(i);

            long start = (long) ((modNumbers.get(i) * Math.ceil(t)) - MIN);

            for (long j = start; j < numbers.length; j += modNumbers.get(i)) {
                numbers[(int) j] = true;
            }
        }

        int count = 0;

        for (int i = 0; i < numbers.length; i++) {
            if (!numbers[i]) {
                count++;
            }
        }

        System.out.println(count);
    }
}