Educational Codeforces Round 54 (Rated for Div. 2) B. Divisor Subtraction(思维)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n;

bool Check(ll num){
	if(num == 1)return false;
	if(num == 2 || num == 3){
		return true;
	}
	if(num % 6 != 1 && num % 6 != 5){
		return false;
	}
	for(ll i = 5; i*i <= num; i += 6){
		if(num % i == 0 || num % (i+2) == 0){
			return false;
		}
	}
	return true;
}


int main()
{
  cin>>n;
  if(n % 2 == 0){
    cout<<n / 2<<endl;
  }
  else{
    ll cnt = 0;
    ll ans;
    if(Check(n)){
      cout<<"1"<<endl;
    }
    else{
      while(n){
        ll i;
        for(i=2;i<=n;i++){
          if(n % i == 0){
            break;
          }
        }
        n -= i;
        cnt ++;
        if(Check(n)){
          cout<<cnt+1<<endl;
          break;
        }
        if(n % 2 == 0){
          cout<<cnt+n/2<<endl;
          break;
        }
      }
    }
  }
  return 0;
}