[수학/브루트포스] 백준 1016 제곱 ㄴㄴ수 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1016번: 제곱 ㄴㄴ 수

 

 

 

2. 문제 풀이

 min과 max가 주어집니다. 두 정수 사이에서 제곱수의 배수가 아닌 수를 판별하여 개수를 구하는 문제입니다.

 

2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

 어렵게 느껴지지만, 때로는 정공법이 가장 간단한 솔루션이 될 수 있습니다. 문제에서 제시한대로 따라하며 답을 찾습니다.

 

 

3. 코드

min_num, max_num = map(int, input().split())
val = [1 for i in range(max_num - min_num + 1)]
cnt=0
i=2
while i**2 <= max_num:
    mul = min_num // i ** 2
    while mul * (i**2) <= max_num:
        if mul * (i**2) - min_num >= 0 and mul * (i ** 2) - min_num <= max_num-min_num:
            val[mul * (i**2) - min_num] = 0
        mul +=1
    i +=1

print(sum(val))

 max가 넘어갈 때까지, 제곱수를 구해서 나누어지는지 확인합니다. 만약 나누어지지 않는다면 해당 수는 제곱 ㄴㄴ수입니다.