🔗 Full Problem 1016

A number $X$ is called a squarefree number when it is not divisible by any square number greater than 1. A square number is the square of an integer. Given min and max, print how many squarefree numbers exist between min and max, inclusive.

The first line gives two integers, min and max.

On the first line, print how many squarefree numbers exist in the interval [min, max].

• $1 ≤ \text{min} ≤ 1,000,000,000,000$
• $\text{min} ≤ \text{max} ≤ \text{min} + 1,000,000$

• Input

TC
1 10

• Output

TC
7

This problem is about counting how many numbers in the given interval are NOT divisible by any square number (4, 9, 16, etc.).

The concept is simpler than it looks. If you know the Sieve of Eratosthenes, you can approach this fairly easily. Surprisingly, the real difficulty lies elsewhere.

1. The maximum value of min and max is on the order of a trillion.
2. The interval doesn't necessarily start at 1.
3. Array indices must be int data only.

Given that the maximum value of the ordinary integer type int is around 2.1 billion, that's nowhere near big enough. So using long is mandatory. On the other hand, array indices can only use int data, so you need to carefully declare and convert between int and long where appropriate.

Although the minimum value min and maximum value max can each be very large, the difference between them never exceeds a million, so there's no issue handling this with an array.

For example, if min = 1,000,000,000,000 (one trillion) and max = 1,000,000,500,000 (one trillion, 500 thousand), the actual interval we need to compare is only about 500,000 numbers. If we represent this interval as array $A$, then $A[0] = 1,000,000,000,000\text{(min)}$. In other words, we need to work with $A[i] = i + \text{min}$.

Since we need to exclude multiples of square numbers, this is very similar to the concept of the Sieve of Eratosthenes, which determines primes by excluding multiples of primes. In other words, we just need to slightly modify the Sieve of Eratosthenes algorithm to identify multiples of square numbers instead of primes.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

/**
 * 백준 전체 1016 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/23/a1016">1016 풀이</a>
 * @since 2021.06.23 Fri 00:22:31
 */
public class Main
{
	// 최소값
	private static long min;
	
	// 최대값
	private static long max;
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		long[] temp = Arrays.stream(reader.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
		
		min = temp[0];
		max = temp[1];
		
		writer.write(Integer.toString(solve()));
		writer.newLine();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 알고리즘 결과 반환 함수
	 *
	 * @return [int] 제곱수로 나누어 떨어지지 않는 수의 갯수
	 */
	private static int solve()
	{
		int size = 0;
		
		boolean[] isNotPow = eratosthenes();
		
		for (boolean item : isNotPow)
		{
			// 제곱수로 나누어 떨어지지 않는 수일 경우
			if (!item)
			{
				size++;
			}
		}
		
		return size;
	}
	
	/**
	 * 에라토스 테네스의 체 배열 반환 함수
	 * true: 제곱ㄴㄴ수가 아닌 수
	 * false: 제곱ㄴㄴ수
	 *
	 * @return [boolean[]] 에라토스 테네스의 체 배열
	 */
	private static boolean[] eratosthenes()
	{
		int length = (int) (max - min + 1);
		
		boolean[] isNotPow = new boolean[length];
		
		for (long i = 2; i * i <= max; i++)
		{
			long pow = i * i;
			
			long start = min % pow == 0 ? min / pow : (min / pow) + 1;
			
			for (long j = start; j * pow <= max; j++)
			{
				// 제곱수의 배수로 나누어 떨어지므로 제곱ㄴㄴ수가 아님
				isNotPow[(int) (j * pow - min)] = true;
			}
		}
		
		return isNotPow;
	}
}

The solve() method is just simple counting logic, so it's enough to understand its intent. The key part is the modified Sieve of Eratosthenes code below.

JAVA
/**
 * 에라토스 테네스의 체 배열 반환 함수
 *
 * true: 제곱ㄴㄴ수가 아닌 수
 * false: 제곱ㄴㄴ수
 *
 * @return [boolean[]] 에라토스 테네스의 체 배열
 */
private static boolean[] eratosthenes()
{
	int length = (int) (max - min + 1);
	
	boolean[] isNotPow = new boolean[length];
	
	for (long i = 2; i * i <= max; i++)
	{
		long pow = i * i;
		
		long start = min % pow == 0 ? min / pow : (min / pow) + 1;
		
		for (long j = start; j * pow <= max; j++)
		{
			// 제곱수의 배수로 나누어 떨어지므로 제곱ㄴㄴ수가 아님
			isNotPow[(int) (j * pow - min)] = true;
		}
	}
	
	return isNotPow;
}

There are two nested loops in total, with indices $i$ and $j$.

• $i$: the square root of the square number
• $j$: an index used to find multiples of the square number

Since the smallest square number greater than 1 is 4, index $i$ starts at 2, and iterates until the square number $i^2$ exceeds max. For example, if the interval is from 10 to 30, $i$ would go from 2 (4) up to 5 (25).

Index $j$ is a bit more complex, due to the existence of the interval. Normally the Sieve of Eratosthenes starts from 1, so there's no issue, but in this problem there's a case where the starting value isn't 1.

For example, suppose $i = 2$ and the interval is from 10 to 20. Since $i^2 = 4$, we need to remove multiples of the square number 4. If we start the multiplication index from 1 as usual, giving us $4 \times 1$, $4 \times 2$, and so on, there's a problem — the interval starts at 10, but we'd end up removing 4 and 8, which are below 10, so those need to be filtered out. If the interval starts at 1000, this results in 250 wasted computations. Given that the interval can start as high as one trillion, we need to properly calculate the multiplication index $j$ based on where the interval starts.

When $i = 2$, $i^2 = 4$. If the interval starts at 10, the numbers $4 \times 1$ and $4 \times 2$, which are below 10, should be skipped, so the multiplication index $j$ should start at 3.

$$j_{\text{min}} = \begin{cases} \text{min} \div i^2 \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, (\text{min} \,\,\, \% \,\,\, i^2 == 0)\\ (\text{min} \div i^2) + 1 \,\,\, (\text{min} \,\,\, \% \,\,\, i^2 \,\,\, != 0) \end{cases}$$

In other words, the general formula for the starting value of multiplication index $j$ is as above.

Since $\text{multiple of a square number} = j \times i^2 \,\,\, (j = 1, 2, 3, \dots)$, we just need to exclude all such values. However, since $j \times i^2$ is the actual value, the array index is $(j \times i^2) - \text{min}$.

The reason we assign true in the array is because the default value of boolean[] is false. We could use the Arrays.fill() method to initialize it to true, but that would be a semantically nicer but unnecessary operation, so we treat false as squarefree and true as not squarefree. That's also why the array is named isNotPow.

After that, all that's left is to iterate over the isNotPow array and count only the values that are false.

• Mathematics
• Number Theory
• Primality Testing
• Sieve of Eratosthenes