链接

[http://codeforces.com/contest/1076/problem/B]

题意

给你一个小于1e10的n,进行下面的运算，n==0 结束，否则n-最小质因子，问你进行多少步

分析

显然n为偶数时，，就会一直-2，不是偶数的话可能是合数或者素数

只需要找根号n内就可以找到合数的最小质因子，否则就是质数

一个奇数-一个奇数一定是偶数，看代码吧

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int main(){

	ll n;

	while(cin>>n){

		bool flag=0;

		ll i;

		for(i=2;i*i<=n;i++)

			if(n%i==0){

				flag=1;

				break;

			}

	if(flag)	cout<<(n-i)/2+1<<endl;

	else cout<<1<<endl;

	}

	return 0;

}