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

题目链接：http://codeforces.com/contest/1076/problem/B

      题意是输入一个n，求出n的最小质因数d，然后n减去d，每减一次算一次操作，问需要减多少次才能使n减为0

      思路就是分情况讨论，对于偶数来说最小的质因数就是2，所以直接除以2就好了，对于奇数来说，如果这个数是素数，直接减去它本身操作1次就够了，如果不是素数我们就求出它的最小质因数，然后用n减去它，记录减去的次数，直到n变成素数或者偶数就好了。

AC代码：

#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;
}