学步园

现在有一个数x，1 ≤ x≤ n，告诉你n，每次你可以猜一个数y，如果x==y则结束，否则返回gcd(x,y)，问最少只要几次就可以保证猜出答案。

Input 

The input file contains several test cases, each of them as described below.

The input contains one integer n, 2n10000.

Output

For each test case, write to the output on a line by itself.

Output one integer -- the number of guesses Andrew will need to make in the worst case.

Sample Input

6

Sample Output

2

首先把所有n以内素分组，每次询问一组素数的积——根据Gcd的性质确定这个数

每次贪心拿一个大质数与一堆小质数配（最右X最左）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
#define MAXN (10000)
#define eps (1e-9)
#define For(i,n) for(int i=1;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
int n,a[MAXN],size=0;
bool b[MAXN];
int main()
{
	memset(b,0,sizeof(b));b[1]=1;
	Fork(i,2,MAXN)
	{
		if (!b[i]) b[i]=1,a[++size]=i;
		For(j,size)
		{
			if (i*a[j]>MAXN) break;
			b[i*a[j]]=1;
			if (!i%a[j]) break;
		}
	}
//	For(i,100) cout<<a[i]<<' ';
	while (cin>>n)
	{
		int i=0,head=1,tail=size;
		while (a[tail]>n) tail--;
		while (head<=tail)
		{
			int p=a[tail];
			while (p*a[head]<=n) p*=a[head++];
			tail--;i++;
		}
		cout<<i<<endl;		
	}	
	return 0;
}