#include <iostream>
using namespace std;
int prim[50000];//用來(lái)存所有素?cái)?shù) 
int primNum=0;//用來(lái)記錄 prim數(shù)組中已經(jīng)存入的素?cái)?shù)的數(shù)量 
int times=0; //用于記錄求解問(wèn)題的總共判斷次數(shù) 
int primLessN(int n);
int primLessN_2(int n);
bool isPrimMothed(int n); //判斷一個(gè)數(shù)是否為素?cái)?shù) 

/*
  方法一：由前往后用素?cái)?shù)判斷的枚舉法：
  求“小于N的最大素?cái)?shù)”中的條件是“n不能被[2,n)中任意一個(gè)素?cái)?shù)整除”，而不是整數(shù)
   
  當(dāng)n=10 0000時(shí)，
  ans=99991
  times=4626 4478次 
  primNum=9592 
  
  我每一個(gè)素?cái)?shù)被判斷出來(lái)，都要遍歷一下之前的素?cái)?shù)表
  而判斷10 0000的時(shí)候，外層循環(huán)走了50000，里層每一個(gè)素?cái)?shù)就是一次之前素?cái)?shù)表的遍歷
  50000*（1+2+3+...+9592)=50000* 4600 8082
  前面那個(gè)數(shù)沒(méi)有50000，還要減去那些非素?cái)?shù) 
  從 50000* 4600 8082可以看出，主要是之前那些素?cái)?shù)花的時(shí)間，非素?cái)?shù)幾乎沒(méi)花時(shí)間
  非素?cái)?shù)= 4626 4478-4600 8082= 25 6450 
  只有25萬(wàn)，雖然還是要比下面多很多，因?yàn)槭菑那巴蟊容^的 
*/
int primLessN(int n)
{
  prim[0]=2; //2是最小的素?cái)?shù)
  primNum++; 
  for(int i=3;i<n;i+=2){
    bool isPrim=1; //isPrim用來(lái)判斷一個(gè)數(shù)是否為素?cái)?shù)
    for(int j=0;j<primNum;j++){
      times++;
      if(i%prim[j]==0){
        isPrim=0;
        break; //沒(méi)加break之前， 當(dāng)n=10 0000時(shí)，times=2 5239 6936次 （2.5億） ，加了之后times=4626 4478次 （4.5千萬(wàn)次） 
      }
      
    } 
    if(isPrim) prim[primNum++]=i;//如果是素?cái)?shù)，則存入prim素?cái)?shù)數(shù)組 
  } 
  return prim[primNum-1];
} 

/*
  方法二： 由后往前的整數(shù)枚舉法
  而且方法二的空間消耗也少 
   
  當(dāng)n=10 0000時(shí)，
  ans=99991
  times=346次 

  當(dāng)n=100 0000時(shí)，用方法一的話，根本算不出來(lái) 
  ans=99 9983
  times=1811次 
  
  當(dāng)n=1 0000 0000(一億)時(shí)， 
  ans=9999 9989
  times=11314次 
  
  當(dāng)n=10 0000 0000(十億)時(shí)， 
  ans=9 9999 9937
  times=52537次 
*/
bool isPrimMothed(int n){
  bool isPrim=1; //isPrim用來(lái)判斷一個(gè)數(shù)是否為素?cái)?shù)
  if(n==2||n==3) return 1;
  for(int i=2;i*i<=n;i++){
    times++;
    if(n%i==0) return 0;
  } 
  return 1;
} 

int primLessN_2(int n){
  for(int i=n;i>=2;i--){
    if(isPrimMothed(i)) return i;
  } 
}
int main(){
  int n;
  scanf("%d",&n);
  //int ans=primLessN(n);
  int ans=primLessN_2(n);
  cout<<ans<<endl; 
  printf("總判斷次數(shù)times:%d\n",times); 
  printf("總素?cái)?shù)數(shù)primNum:%d\n",primNum); 
  return 0;
}