using System;
using System.Collections.Generic;
using RedCorona.Utils;

class Factor{
 public static List<decimal> factor(decimal n){
  List<decimal> factors = new List<decimal>();
  while(n != 2 && !(n % 2)){
   n /= 2;
   factors.Add(2);
  }
  while(n != 3 && !(n % 3)){
   n /= 3;
   factors.Add(3);
  }
  for(decimal i = 5, s = 2; i <= isqrt(n); i += 2 + (s = s + 2 % 4))
   while(n != i && !(n % i)){
    n /= i;
    factors.Add(i);
   }
  factors.Add(n);
  return factors;
 }

 public static List<ulong> factor(ulong n){
  List<ulong> factors = new List<ulong>();
  while(n != 2 && !(n % 2)){
   n /= 2;
   factors.Add(2);
  }
  while(n != 3 && n != 3 && !(n % 3)){
   n /= 3;
   factors.Add(3);
  }
  for(ulong i = 5, s = 2; i <= isqrt(n); i += 2 + (s ^= 2))
   while(n != i && !(n % i)){
    n /= i;
    factors.Add(i);
   }
  factors.Add(n);
  return factors;
 }

 public static List<LargeInteger> factor(LargeInteger n){
  List<LargeInteger> factors = new List<LargeInteger>();
  while(n != 2 && !(n % 2)){
   n /= 2;
   factors.Add(2);
  }
  while(n != 3 && !(n % 3)){
   n /= 3;
   factors.Add(3);
  }
  for(ulong i = 5, s = 2; i <= isqrt(n); i += 2 + (s = s + 2 % 4))
   while(n != i && !(n % i)){
    n /= i;
    factors.Add(i);
   }
  factors.Add(n);
  return factors;
 }

 public static ulong isqrt(ulong n){
  ulong r = 0;
  for(ulong i = 0x4000000000000000; i; i >>= 2)
   if(n >= (i | r)){
    n -= i | r;
    r = r >> 1 | i;
   } else r >>= 1;
  return r;
 }

 public static decimal isqrt(decimal n){
  decimal i;
  for(i = 1; i <= n; i += 2) n -= i;
  return((i / 2).Truncate());
 }

 public static LargeInteger isqrt(LargeInteger n){
  LargeInteger r = 0;
  for(LargeInteger i = (LargeInteger)1 << (n.Size * 32) - 2; i; i >>= 2)
   if(n >= (i | r)){
    n -= i | r;
    r = r >> 1 | i;
   } else r >>= 1;
  return r;
 }
}