(Python/🥇1)백준알고리즘 1016번: 제곱 ㄴㄴ수

 

문제 바로가기 

문제:

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

입력:

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

 

출력:

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

 

풀이:

제한사항이 엄청나다 10^12 승이다.

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

X, Y = map(int, sys.stdin.readline().split(" "))
res = Y - X + 1  
board = [False] * res  

for i in range(2, int(Y ** 0.5) + 1):  # 2부터 Y의 제곱근까지 반복
    j = i ** 2  # 제곱수를 계산

    # 제곱ㄴㄴ수를 판별할 범위 내에서 시작값 계산
    start = (X // j) * j
    if start < X:
        start += j

    # 배수를 차례로 탐색
    for k in range(start, Y + 1, j):
        if not board[k - X]:  # 아니라면
            board[k - X] = True  #체크
            res -= 1  # 개수 감소

print(res)  # 출력

 

start 는 가장 작은값보다 큰 제곱수로 나눠지는 값이다.

처음은 j 가 4이므로

만약 X = 55이면 52가 나온다. 그러면 4를 한번 더 더해주고 그 값부터 시작.

 

 0부터 시작하기 때문에 수열의 원소와 인덱스를 맞추기 위해 k - X를 사용한다.

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

X, Y = map(int, sys.stdin.readline().split(" "))
res = Y - X + 1
board = [1] * res
lst = [i**2 for i in range(2, int(Y ** 0.5) + 1)]
for i in lst:
    start = (X//i)*i
    while start < Y+1:
        if start - X >= 0:
            board[start-X] = 0
        start += i
print(sum(board))

 

이 방법도 된다고 한다. 밑 방법이 더 편해보인다.

n이 시작값을 설정해준다. 

 

골1인데 괜찮았다??