BOJ 25921 - 건너 아는 사이

BOJ 25921 - 건너 아는 사이

MST문제처럼 보이지만 에라토스테네스의 체를 써서 푸는 문제이다.

$2$의 배수는 모두 $2$와 친구가 되는것이 이득이다.

$2$가 가장 작은 서로소가 아닌 소인수이기 때문이다.

마찬가지로 $3$의 배수 중에서도 $2$의 배수가 아닌것들은 $3$과 이어주고 쭉 해주면 된다.

그리고 각 소수들은 $1$과 이어주어야 하므로 소수들도 정답에 더한다.

void solve() {
   int n, ans = 0;
   cin >> n;
   vi used(n + 1);
   for (int i = 2; i <= n; i++) {
      if (!used[i]) {
         used[i] = 1;
         ans += i;
         for (int j = i * 2; j <= n; j += i) {
            if (!used[j]) {
               ans += i;
               used[j] = 1;
            }
         }
      }
   }
   cout << ans;
}