[lv4] 1016. 제곱 ㄴㄴ수 (Python 파이썬 풀이)

[lv4] 1016. 제곱ㄴㄴ수(Python 파이썬 풀이)

출처

www.acmicpc.net/problem/1016

문제

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

입력

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

출력

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

제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

입력	출력
1 10	7

해석

문제의 제한을 보면 min값이 최대 1,000,000,000,000 까지 된다. 이에 비해 최소값과 최대값의 차이는 최대 1,000,000까지 이므로 우리는 메모리크기를 최소화 하기 위해서 1,000,000개의 범위 내에서 찾도록 한다. 일반적으로 소수의 풀이는 에라토스테네스의 체를 이용하여 풀이하였다. 어떠한 숫자 n이 있을 때 방문 리스트를 이용하는데에 있어서 n이 소수라면 vi[n]=False라고 하면서 풀었을 것이다. 이는 0으로부터 n칸 떨어진 지점이 False라고 나타난 값이라고 볼 수 있다. 이 문제에선 관점을 달리하여 0으로부터 떨어진 지점이 보는 것이 아니라 a로부터 n칸이 떨어진 지점이 소수인지 아닌지를 판별하면 된다. 이제는 0부터가 아니라 i**2-a%(i**2)부터이고 i**2칸 마다 확인을 하면 된다.

제출 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

import sys def my_sqrt(a,b):     for i in range(2,int(b**0.5)+1):         n = i**2-a%(i**2)         if n==i**2:             n=0         while n <= (b-a):             if vi[n]:                 vi[n] = False             n += i**2   a,b = map(int,sys.stdin.readline().split()) vi = [True]*(b-a+1) my_sqrt(a,b) ans = 0 for i in vi:     if i:         ans += 1 print(ans) Colored by Color Scripter

cs