import java.math.*;
import java.io.*;
//==========================================================C
//  OS(Quadratic Sieve) Program                             C
//  2次ふるい法javaプログラム 原理プログラム                C
//----------------------------------------------------------C
//   1. M = (int)sqrt(N)                                    C
//        using Bsqrt                                       C
//   2. Seting the Factor Base                              C
//        Prime Table:  PTB[NP]                             C
//        Factor Base:  FTB[NB]                             C
//   3. Sieving by QS                                       C
//        Sieved Matrix: MQS[ND][NB]                        C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/07/27              C
//        ( Tokyo Kougei University )                       C
//        後 保範： 東京工芸大学                            C
//==========================================================C
public class TQS{ 
public static void main (String[] args) throws Exception
 { String s;
   int k, j;
   int NV[] = new int[2];
   BigInteger N, M;
   int NB, ND;
   long t1,t2,t3,t4;
   double T1,T2,T3;
//  IO=0 --> 分解結果だけ出力、IO=1 --> 途中情報出力
//  IO=2 --> 行列及び分解行列出力
   int IO=2;
//  I/O File set
   FileInputStream fi = new FileInputStream("in.txt");
   InputStreamReader in = new InputStreamReader(fi);
   BufferedReader bin = new BufferedReader(in);
   FileOutputStream fo = new FileOutputStream("Sieve.txt");
   PrintWriter out = new PrintWriter(fo,true);
   s = bin.readLine();
   N = new BigInteger(s);
   out.println("2次ふるい法による因数分解");
//  QS
   t1 = System.currentTimeMillis();
   int NP = 16;
   QS q = new QS();
   M = q.QS(N, NP, NV);
   NB = NV[0];  ND = NV[1];
   out.println("分解対象数="+N.toString()+", 平方根="
                +M.toString());
   out.println("基底="+NB+", データ="+ND+ ", ふるい数="+q.NOS);
   if(IO >= 1)
    { for (k=0; k<NB; k++)
       { out.print(q.FTB[k]+" "); }
      out.println("");
    }
   if(IO >= 2)
    { for (k=0; k<ND; k++)
       { BigInteger S = q.MX[k];
         S = S.multiply(S);
         S = S.subtract(N);
         out.print(k+" "+q.MX[k].toString()+" "+S.toString());
         for (int i=0; i<NB; i++)
           { out.print(" "+q.MQS[k][i]); }
         out.println("");  }
    }
//  Gauss Elimination
   t2 = System.currentTimeMillis();
   int ID = q.Gauss(ND, NB);
   if(IO >=1 ) out.println("従属数="+ID);
   t3 = System.currentTimeMillis();
//  Output AM & EM
   if(IO >= 2)
    { out.println("A+E");
      for (k=0; k<ND; k++)
       { out.print(k+"  ");
         for (int i=0; i<NB; i++)
          { out.print(q.AM[k][i]+" "); }
         for (int i=0; i<ND; i++)
          { out.print(" "+q.EM[k][i]); }
         out.println("");
       }
    }
//  Factorization
   q.Factor(N, M, ND, NB, ID); 
   for (k=0; k<ID; k++)
    { out.println("k="+k);
      if(IO >= 1)
       { int NN = q.LN[k][0];
         for (j=1; j<=NN; j++)
          { out.print(q.LN[k][j]+" "); }
         out.println("");
         for (j=0; j<NB; j++)
          { out.print(q.PW[k][j]+" "); }
         out.println("");
         out.print("X="+q.FactV[k][0].toString());
         out.println(" Y="+q.FactV[k][1].toString());
       }
      out.print("P="+q.FactV[k][2].toString());
      out.println(" Q="+q.FactV[k][3].toString());
    }
   t4 = System.currentTimeMillis();
   T1 = (t4 - t1)/1000.0;
   T2 = (t2 - t1)/1000.0;
   T3 = (t3 - t2)/1000.0;
   out.println("Total="+T1+", Sieve="+T2+", Gauss="+T3);
  }
}