백준 1016번 [제곱 ㄴㄴ 수](C++)-yes6686- 티스토리

백준 문제 풀이: 1016 [제곱 ㄴㄴ 수]

---

문제 링크: https://www.acmicpc.net/problem/1016

문제 설명:

두 정수 n과 m이 주어질 때, n 이상 m 이하의 정수 중 제곱 ㄴㄴ 수(어떤 소수의 제곱으로 나눠지지 않는 수)의 개수를 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

long long int arr[1000001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long int n, m;
    cin >> n >> m;
    
    for (long long int i = 2; i * i <= m; i++) {
        long long int k = n / (i * i);
        if (n % (i * i)) k++;
        
        for (long long int j = k * (i * i); j <= m; j += (i * i)) {
            arr[j - n] = 1;
        }
    }
    
    int ans = 0;
    for (int i = 0; i <= m - n; i++) {
        if (!arr[i]) {
            ans++;
        }
    }
    cout << ans;
}

---

코드 설명

• 핵심 알고리즘: 소수의 제곱들을 이용해 범위 내 숫자 중 제곱 ㄴㄴ 수를 걸러냅니다.
• 구현 세부사항:
  • 모든 소수의 제곱을 구하고, 각 제곱으로 나눠지는 수들을 제거합니다.
  • 배열 arr를 이용해 n에서 m까지의 숫자 중 제거되지 않은 수를 카운트합니다.
• 시간 복잡도: O((m - n) log log sqrt(m))
  • 소수 구하기: O(sqrt(m) log log sqrt(m))
  • 제곱 ㄴㄴ 수 필터링: O((m - n) log sqrt(m))

---

결과

n에서 m까지의 정수 중 제곱 ㄴㄴ 수의 개수를 효율적으로 계산합니다. 범위가 매우 크기 때문에 메모리와 시간 효율성을 고려한 방식으로 구현했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!