[BOJ] 1016

less than 1 minute read

제곱 ㄴㄴ 수

1016번 https://www.acmicpc.net/problem/1016

(ab)2 은 a2으로도, b2으로도 나눠집니다.
즉, 어떤 수 x가 소수가 아니라면, x2은 다른 제곱수의 배수입니다.

따라서, min과 max가 주어졌을 때,
min과 max사이의 수 중 소수의 제곱수로 나눠떨어지는 수들만 생각해줘도
소수가 아닌 수의 제곱수로 나눠떨어지는 수들은 모두 포함되므로
소수의 제곱수로 나눠떨어지는 수들만 체크해주면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/1016.cpp

Categories:

Updated:

Leave a comment