Determine the number of subtrations the algorithm will make.

Input

The only line contains a single Integer n (2≤n≤10,2≤n≤10).

Output

Print a single Integer — the number of subtractions the algorithm will make.

Examples

input

5

output

1

input

4

output

2

Note

In the first example 5 is the smallest prime divisor, thus it gets subtracted right away to make a 0.

In the second example 2 is the smallest prime divisor at both steps.

题意

将一个数n减去其最小质因数，若差为0，则终止进程，否则，重复减去最小质因数的操作。

统计一下相减的次数。

思路（复盘）

1. 按照题意发现，若数为偶数，其最小质因数为2，减完后其仍然为偶数，其最小质因数仍然为2，此时将会一直减2，直到为0。
2. 质数按奇偶性分，可将2单独归为一类，另将其他非2的归为一类。而结合思路1可知，我们需要着重考虑的是当n为奇数的情况，而当n为奇数时，其最小质因数必不为偶数，为奇数，且当奇数减去奇数质因数时，结果为偶数，从而进入到思路1的解法中。

#include<bits/stdc++.h>
using namespace std;

long long get_prime(long long n)
{
	for(long long i=2;i*i<=n;i++)
	{
		if(n%i==0)
		   return i;
	}	   return n;
}
int main()
{
	long long n,cnt=0;
	cin>>n;
    if(n%2!=0)
	{
	    n=n-get_prime(n);   
	    cnt++;
	}
	
	cout<<cnt+n/2;
	return 0;
}

大佬总结

以上是大佬教程为你收集整理的336494 B. Divisor Subtraction全部内容，希望文章能够帮你解决336494 B. Divisor Subtraction所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。