[백준 1016] 제곱 ㄴㄴ 수 (C#, C++) - soo:bak

문제 링크

1016번 - 제곱 ㄴㄴ 수

설명

min 이상 max 이하의 정수 중에서, 1보다 큰 어떤 정수의 제곱으로도 나누어떨어지지 않는 수의 개수를 구하는 문제입니다. 이러한 수를 제곱 ㄴㄴ 수라고 부릅니다.

접근법

구간의 길이가 최대 100만이므로, 구간 전체를 배열로 만들어 에라토스테네스의 체와 비슷한 방식으로 해결할 수 있습니다.

먼저, 구간의 길이만큼 배열을 만들고 모든 값을 참으로 초기화합니다. 배열의 i번 인덱스는 구간의 시작값에 i를 더한 수가 제곱 ㄴㄴ 수인지를 나타냅니다.

다음으로, 2부터 시작하여 제곱한 값이 구간의 끝값 이하인 동안 반복합니다. 각 수의 제곱에 대해, 구간 내에서 그 제곱으로 나누어떨어지는 수들을 모두 거짓으로 표시합니다.

이때 구간 내 시작점을 구하는 것이 핵심입니다. 구간의 시작값을 제곱수로 나눈 몫을 올림한 뒤 다시 제곱수를 곱하면 구간 내 첫 번째 배수가 됩니다. 이 시작점부터 구간의 끝값까지 제곱수씩 증가하며 해당 위치를 거짓으로 표시합니다.

모든 제곱수에 대한 처리가 끝나면 배열에서 참으로 남아있는 수의 개수가 제곱 ㄴㄴ 수의 개수입니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var parts = Console.ReadLine()!.Split();
    var mn = long.Parse(parts[0]);
    var mx = long.Parse(parts[1]);

    var len = (int)(mx - mn + 1);
    var ok = new bool[len];
    for (var i = 0; i < len; i++) ok[i] = true;

    for (var i = 2L; i * i <= mx; i++) {
      var sq = i * i;
      var n = mn / sq;
      if (mn % sq != 0) n++;
      var val = n * sq;
      for (; val <= mx; val += sq)
        ok[val - mn] = false;
    }

    var ans = 0;
    for (var i = 0; i < len; i++) if (ok[i]) ans++;
    Console.WriteLine(ans);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll mn, mx; cin >> mn >> mx;
  int len = (int)(mx - mn + 1);
  vector<char> ok(len, 1);

  for (ll i = 2; i * i <= mx; i++) {
    ll sq = i * i;
    ll n = mn / sq;
    if (mn % sq != 0) n++;
    ll val = n * sq;
    for (; val <= mx; val += sq)
      ok[val - mn] = 0;
  }

  int ans = 0;
  for (int i = 0; i < len; i++) if (ok[i]) ans++;
  cout << ans << "\n";

  return 0;
}