#include <stdio.h>

 #include <stdlib.h>

 #define SIZE 1000020

 int prime[SIZE];//来保存素数，从下标1开始保存第一个

 int temp[SIZE];//这个是用素数筛选法求出的素数

 int maxPrimeFactor(int n)//求最大素因子的函数

 {

     int ans;

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

     {

         while(n % i == )

         {

             ans = i;//如果能求余， 那么当前的i 就是一个素因子

             n /= i;//将n缩小

         }

     }

     if(n > )//此时说明n 没有被任何一个素数整除， 最大素因子的当然是他本身

         ans = n;

     return ans;

 }

 int main()

 {

 //    freopen("1.txt", "r", stdin);//利用重定向

 //    freopen("2.txt", "w", stdout);

     int N;

     temp[] = ;

     for(int i = ; i < SIZE; i ++)//将整个素数表初始化

         temp[i] = i;

     for(int i = ; i * i< SIZE; i ++)

     {

         if(temp[i] != -)

         {

             for(int j = i * i; j < SIZE; j += i)

                 temp[j] = -;//如果不是素数就将它标记为-1

         }

     }

     int index = ;

     for(int i = ; i < SIZE; i ++)

     {

         if(temp[i] != -)

             prime[index ++] = temp[i];//将素数表中的素数复制到prime数组中

     }

     while(scanf("%d", &N) != EOF)

     {

         if(N == )//特殊数字，特别对待

         {

             printf("0\n");

             continue;

         }

         int left = , right = index - , mid = (left + right) / ;//利用二分法确定最大素数在素数表prime中位置，如果直接for循环会超时

         int maxPrime = maxPrimeFactor(N);

         if(maxPrime == prime[right])//此时下标不是从零开始， 所以只有两个元素时，假如要确定后一个的位置，当前这个二分不行，这个特殊情况单独写出来

         {

             printf("%d\n", right);

             continue;

         }

         while(maxPrime != prime[mid])

         {

             if(maxPrime > prime[mid])

                 left = mid;

             else

                 right = mid;

             mid = (left + right) / ;

         }

         printf("%d\n", mid);//打印下标

     }

     return ;

 }