题目链接: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;
}