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

2024. 5. 30. 06:16코딩 도구/백준

반응형

백준 1016 - 제곱 ㄴㄴ 

문제

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

 

1016번: 제곱 ㄴㄴ 수

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

www.acmicpc.net

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

 

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

소수 소수 구하기의 핵심 이론 소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체를 들 수 있다. 에라토스테네스의 체 원리는 다음과 같다. ① 구하고자 하는 소수의 범위만큼 1차원 리

mkisos.tistory.com

 

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

 

정수론 : 오일러 피

오일러 피 오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 오일러 피 함수는 증명 과정을 공부해야 완벽하게 알 수 있다고하지만 실제 코딩 테스트에

mkisos.tistory.com

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

 

정수론 : 유클리드 호제법

유클리드 호제법 유클리드 호제법 euclidean-algorithm은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현

mkisos.tistory.com

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

 

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

확장 유클리드 호제법 유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것이다. 확장 유클리드 호제법을 제대로 이해하

mkisos.tistory.com

 

반응형