(BOJ1016 제곱 ㄴㄴ 수

• tags : (algorithm

  No matching post could be found

• 문제 링크 : https://www.acmicpc.net/problem/1016
• 풀이 링크
  • Python

• 가장 간단하게 설명하면, 특정 구간에서 특정 조건을 만족하는 수의 갯수를 구하는 문제이다.
• 조금 더 상세하게 살펴보면, 구간은 최대 100만 개의 숫자를 포함하고, 정답에서 제외해야 하는 숫자는 어떤 수의 제곱의 배수인 경우이다.
  • 만약 모든 숫자를 어떤 수의 제곱의 배수인지 확인한다고 하면 하나의 숫자를 확인하기 위해 그 수의 제곱근까지 모든 수를 확인해야 한다. 이는 O(logN)의 시간이 걸린다.
• 대신 단계를 조금 줄여보는 방향으로 생각해볼 수 있다.
  • 입력으로 주어지는 max값의 제곱근까지의 수를 탐색하고, 해당 숫자들의 제곱의 배수를 찾으면 된다.
  • 조금 더 단계를 줄인다면, max값의 제곱근까지의 수 중 소수만 탐색하여 해결할 수 있다.

min_val, max_val = map(int, input().split())
check = [False] * (max_val - min_val + 1)
ans = max_val - min_val + 1
for n in range(2, int(max_val**0.5) + 1):
    n_square = n * n
    q = min_val // n_square + 1 if min_val % n_square else min_val // n_square
    q_max = max_val // n_square + 1
    for k in range(q, q_max):
        if not check[n_square * k - min_val]:
            check[n_square * k - min_val] = True
            ans -= 1
print(ans)

• max의 제곱근까지의 모든 숫자를 탐색하는 경우
• 정답을 구하기 위하여 min부터 max까지 구간 확인을 위한 리스트를 생성한다.
  • 이 때, 입력되는 수는 1조까지 나올 수 있으므로 전체 숫자를 확인하는 리스트 대신, min부트 max까지 값만 확인할 수 있는 리스트로 선언
  • 또한 count()메서드 등을 활용하여 답을 구할 수 있지만, ans값에 답을 저장하며 확인함
• 2부터 max의 제곱근까지 모든 수를 탐색하는 for문을 구성했고,
  • 해당 수의 제곱과 그 배수를 구하여 에라토스테네스의 체를 적용했다.

min_val, max_val = map(int, input().split())
check = [True] * (max_val - min_val + 1)

if max_val <= 3:
    print(max_val - min_val)
    exit()
prime_square = [4]
max_sqrt = int(max_val**0.5)
is_prime = [True] * (max_sqrt // 2 + 1)
for i in range(3, max_sqrt + 1, 2):
    if is_prime[i // 2]:
        i_square = i * i
        prime_square.append(i_square)
        is_prime[i_square // 2 :: i] = [False] * (
            (max_sqrt - i_square + 1) // (2 * i) + 1
        )
for num in prime_square:
    st = num - min_val % num if min_val % num else 0
    check[st::num] = [False] * len(check[st::num])
print(check.count(True))

• max값이 4보다 작은 경우 더이상 탐색할 필요가 없기 때문에 조건문을 처리했다
• 아니라면 2이상 max의 제곱근 이하 모든 소수의 제곱을 탐색한다.
  • 여기서 탐색을 더 줄이기 위해 2 * 2 = 4를 먼저 추가하고,
  • 3부터 모든 홀수 중 소수를 탐색한다.
• 소수의 제곱을 구했을 때 min부터 max까지의 값을 다시 탐색하여 정답을 구한다.