백준 1016 파이썬 에라토스테네스의 체 방식으로 제곱수의 배수 형태로 탐색

백준 1016 - 제곱 ㄴㄴ 

문제

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

1016번: 제곱 ㄴㄴ 수

1016번

답안 코드 :

import math

Min, Max = map(int, input().split())

Check = [False] * (Max - Min + 1)

for i in range(2, int(math.sqrt(Max) + 1)):

    pow = i * i

    start_index = int(Min / pow)

    if Min % pow != 0:

        start_index += 1    # 나머지가 있는 경우 1을 더해 Min보다 큰 제곱수에서 시작하도록 설정

    for j in range(start_index, int(Max / pow) + 1):    # 제곱수를 True로 변경

        Check[int((j * pow) - Min)] = True

count = 0

for i in range(0, Max - Min + 1):

    if not Check[i]:

        count += 1

print(count)

생각 :

# 문제 분석
# min의 최댓값이 1,000,000,000,000 으로 매우 큰 것 같지만 
# min , max 사이의 수들 안에서 구하면 되니까
# 1,000,000의 데이터만 확인하면 된다
# 제곱수 판별을 일반적인 반복문 구하면 시간 초과 일 듯
# 에라토스테네스의 체 알고리즘 이용해서 풀장

# 문제 풀이 
# 2의 제곱인 4부터 max 안에 제곱수들 찾기
# 데이터를 순차적 탐색 x
# 에라토스테네스의 체 방식으로 제곱수의 배수 형태로 탐색하기
# 시간복잡도 최소화 !!

 

정수론 정리 글들

 

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B1%84

정수론 : 소수 구하기 에라토스테네스의 채

 

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%98%A4%EC%9D%BC%EB%9F%AC-%ED%94%BC

정수론 : 오일러 피

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

정수론 : 유클리드 호제법

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%ED%99%95%EC%9E%A5-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

정수론 : 확장 유클리드 호제법