제곱 ㄴㄴ수

---

🔗 🔗 전체 1016번 문제

조건

---

문제

---

어떤 수 $X$가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

---

첫째 줄에 두 정수 min과 max가 주어진다.

출력

---

첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다.

제한

---

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

케이스

---

예제 1

---

• 입력

TC
1
1 10

• 출력

TC
1
7

풀이

---

주어진 구간에서 제곱수(4, 9, 16 등)으로 나누어지지 않는 수의 갯수를 구하면 되는 문제.

개념은 생각보다 간단하다. 에라토스 테네스의 체에 대해 알고있다면 생각보다 쉽게 접근할 수 있기도 하고. 의외로 문제는 다른 쪽에 있다.

1. min, max의 최대값이 1조 단위다.
2. 구간이 반드시 1부터 시작하지 않는다.
3. 배열의 인덱스는 반드시 int 데이터만 가능하다.

보편적인 정수 데이터인 int의 최대값이 약 21억인걸 감안하면 턱없이 큰 수. 때문에 long 데이터의 사용이 강제된다. 반면 배열의 인덱스는 int 데이터만 사용 가능하므로, int와 long의 적절한 데이터 선언 및 변환이 필요하다.

최소값 min과 최대값 max는 그 수가 매우 클 수는 있어도, 그 차이는 백만 이하로만 나오므로 배열로 다루는데 무리가 없다.

만약, min = 1,000,000,000,000(1조)이고, max = 1,000,000,500,000(1조 50만)일 경우, 실제로 비교해야할 구간은 약 50만개밖에 되지 않는다. 이 구간을 배열 $A$로 표시하면 $A[0] = 1,000,000,000,000\text{(min)}$가 된다. 즉, $A[i] = i + \text{min}$으로 다뤄야한다.

제곱수의 배수를 제외해야한다는 점에서 소수의 배수를 제외하여 소수를 판별하는 에라토스 테네스의 체의 개념와 매우 흡사하다. 즉, 에라토스 테네스의 체 알고리즘에서 소수가 아닌 제곱수의 배수를 판별하게끔 살짝 변형시켜주면 된다.

전체 소스

---

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
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;
	}
}

solve() 메소드는 단순히 갯수를 파악하는 로직이므로 그 의도만 알면 된다. 가장 핵심인 부분은 에라토스 테네스의 체를 변형한 아래 코드다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 에라토스 테네스의 체 배열 반환 함수
 *
 * 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;
}

총 2개의 반복문이 돌아간다. 인덱스는 각각 $i$, $j$다.

• $i$: 제곱수의 제곱근
• $j$: 제곱수의 배수를 구하기 위한 인덱스

1보다 큰 제곱수는 4이므로, 인덱스 $i$의 시작값은 2이며, 제곱수인 $i^2$의 크기가 max 이하일때 까지 반복한다. 만약, 구간이 10부터 30까지라면, $i$는 2(4)부터 5(25)까지 증가할 것이다.

인덱스 $j$는 약간 복잡한데, 이는 구간의 존재 때문이다. 기본적으로 에라토스 테네스의 체는 1부터 시작하므로 상관없지만, 해당 문제는 시작값이 1이 아닐 경우가 존재한다.

예를 들어, $i = 2$이고 구간이 10 ~ 20까지라고 가정하자. $i^2 = 4$이므로 제곱수 4의 배수를 제거해야한다. 만약 평상시처럼 곱셈의 인덱스를 1부터 시작해서 $4 \times 1$, $4 \times 2$, $\dots$와 같이 시작한다면 문제가 생긴다. 구간은 10부터인데 비해, 10 이하인 4, 8을 제거하게되니 이를 걸러내야한다. 만약 구간이 1000부터 시작이라면 250개의 쓸모없는 연산이 발생한다. 구간이 최대 1조부터 시작할 수 있음을 생각한다면 구간의 시작에 따라 곱셈 인덱스 $j$를 적절히 계산해야한다.

$i = 2$일 경우, $i^2 = 4$이다. 구간의 시작이 10일 경우, 10 이하인 수 $4 \times 1$, $4 \times 2$는 건너뛰므로 곱셈 인덱스 $j$는 3부터 시작해야한다.

즉, 곱셈 인덱스 $j$의 시작값의 일반식은 위와 같다.

$\text{제곱수의 배수} = j \times i^2 \,\,\, (j = 1, 2, 3, \dots)$이므로, 해당값을 모두 제외하면 된다. 단, $j \times i^2$는 실제 값이므로, 배열의 인덱스는 $(j \times i^2) - \text{min}$이다.

배열에 true를 할당하는 이유는 boolean[]의 초기값이 false이기 때문. Arrays.fill() 메소드를 활용하여 true로 초기화할 수도 있으나, 의미론적으론 좋지만 불필요한 연산이므로 false를 제곱ㄴㄴ수로, true를 제곱ㄴㄴ수가 아닌 수로 지칭한다. 배열 이름이 isNotPow인 이유도 이때문.

이후 isNotPow 배열을 순회하며, 값이 false인 수만 카운팅하면 된다.

분류

---

• 수학
• 정수론
• 소수 판정
• 에라토스 테네스의 체