[백준 / BOJ] C++ 9213 꽤 좋은 수

9213번: 꽤 좋은 수

 

문제

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

9213번: 꽤 좋은 수

 

 

풀이

자신을 제외한 약수의 합과 자신의 차가 어떠한 수 이하이면 꽤 좋은 수다. 범위 내 꽤 좋은 수의 개수를 구하는 문제.

 

모든 수에 대해 일일이 약수를 구해 더하면 시간초과가 난다. 그래서 에라토스테네스의 채를 이용해야 한다.

i=1부터 100만까지 1씩 증가하며, j=i*2부터 100만까지 i씩 증가하며 j 인덱스의 배열에 i 만큼 더해준다.

 

위 방식대로 하면 자신은 제외하면서 약수들을 모두 더해줄 수 있다. 배열을 모두 구성했으면 조건대로 처리해주면 된다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  vector<int> sieve(1000001, 0);
  for (int i = 1; i <= 1000000; i++)
    for (int j = i * 2; j <= 1000000; j += i)
      sieve[j] += i;
  int cnt = 1;
  while (1) {
    int s, e, bad, ans = 0;
    cin >> s >> e >> bad;
    if (s == 0)
      break;
    for (int i = s; i <= e; i++) {
      if (abs(sieve[i] - i) <= bad)
        ans++;
    }
    cout << "Test " << cnt << ": " << ans << '\n';
    cnt++;
  }
  return 0;
}