import java.io.*;
import java.math.*;
//==========================================================C
//  NP番までの素数の計算                                    C
//    NP <= NPTB(1千万)                                     C
//    素数の値はPTB[k], k=0〜NP-1に入る                     C
//    IWKは素数ふるいのワークエリア                         C
//==========================================================C
//    作成　後 保範 (Ushiro Yasunori),  2008/09/01          C
//       ( 東京工芸大学 )        　　　　　　　　           C
//==========================================================C
public class Prime{
// 計算領域
 static int PTB[] = new int[10000000];
 static int IWK[] = new int[100000]; 
 static int NPTB=10000000, NIWK=100000; 
//==========================================================C
//  Main Program                                            C
//==========================================================C
public static void main (String[] args) throws Exception
 { int NP, k, j, LC=10;
   long t1, t2;
//  出力ファイルの指定及び画面からNP(素数の数)の入力
   FileOutputStream fo = new FileOutputStream("Prime.txt");
   PrintWriter out = new PrintWriter(fo,true);
   InputStreamReader in = new InputStreamReader(System.in);
   BufferedReader br = new BufferedReader(in);
   System.out.println("求める素数の数を入れてください");
   String input = br.readLine();
   NP = Integer.parseInt(input);
//  NP番までの素数の計算
   t1 = System.currentTimeMillis();
   TPRIM(NP);
   t2 = System.currentTimeMillis();
   double CPU = (t2 - t1)/1000.0;
   System.out.println("計算時間="+CPU+" 秒");
//  素数のファイルへの出力
   for (k=0; k<NP; k=k+LC)
    { out.print(k+": ");
      int KN = Math.min(NP, k+LC);
      for (j=k; j<KN; j++)
       { out.print(" "+PTB[j]); }
      out.println();
    }
 }
//==========================================================C
public static void TPRIM(int NP)
//==========================================================C
//  Setting the Table of Prime Numbers                      C
//   PTB(k) = k's Prime Number                              C
//     k=0,1,...,NP-1,  PTB[0]=2, PTB[1]=3, PTB[3]=5,...    C
//----------------------------------------------------------C
//    NP     int, In,  Size of Prime Table                  C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/09/01              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
 { int i, j, j1,k;
   int NO, LPM, NE, NH, NS, NS1; 
   int NIT[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43};
//  Initial Set
   NO = 14;  LPM = 43;
   for (i=0; i<Math.min(NO,NP); i++)
    { PTB[i] = NIT[i]; }
//  Main Loop of prime numbers
   while (NP > NO)
    { NE = NIWK;
//   NEは奇数に対し、ふるいをおこなう奇数の数
//   NOは求めた最終素数番号
      if(LPM <= 30000) NE = Math.min(LPM*LPM/2, NIWK);
      for (i=0; i<NE; i++)
        { IWK[i] = 0; }
//  Sieve odd composit number
//   NHはふるいをおこなう最大の整数
//    LPM+2*j1, j1=1,2,...,NO-1までの整数をふるう 
      NH = LPM + 2*NE;
      for (j1=1; j1<NO; j1++)
        { j = PTB[j1];    // j1番の素数
//    素数の2乗が最大整数を超えればふるいは終了
          if(j*j > NH) { break; }
          NS1 = j - (LPM+2)%j;
          if(NS1 == j) { NS1 = 0; }
          NS  = (j*(NS1%2) + NS1)/2;
//    NSはLPM+2+2*NSがjで割れる値 (NS<j)
//    NS=(j-(LMP+2)%j)/2が基本であるが()内が奇数と偶数で分かれる
          for (i=NS; i<NE; i+=j)
            { IWK[i] = 1; }   // jで割れる値は1を入れる
        }
//  Search prime number
      for (i=0; i<NE; i++)
        { LPM = LPM + 2;
//    IWK[i]=0なら素数で割れないのでLPMを素数と判定
          if(IWK[i] == 0) 
            { PTB[NO] = LPM;
              NO += 1; }
//    求める素数の数に達したら終了
          if(NO >= NP) { break; }
        }
     }
  }
}