백준 23832 서로소 그래프

문제 : https://www.acmicpc.net/problem/23832

#include <iostream>

using namespace std;
long long N;
long long ans;
long long ret = 0;
long long num;
bool notprime = false;
void input(){
  cin >> N;
}

int phi(int n){
  for(long long i = 2; i * i <= n; i++){
    if(num % i == 0){
      notprime = true;
      ans = ans / i * (i-1);
      while(num % i == 0){
        num /= i; 
      }
    }
  }

  if(!notprime && n!=1){
    ans -= 1;
    return ans;
  }
  else if(num != 1){
    ans = ans / num * (num - 1);
    return ans;
  }
  else return ans;
}

void solve(){
  ans += (N-1); //1이 서로소인 개수
  for(long long i = 2; i <= N; i++){
    num = i;
    ans = i;
    notprime = false;
    ret += phi(i);
  }
  cout << ret;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  input();
  solve();
  return 0;
}