title: n-th prime number problem, need to speed it up a bit
body: <p>There is simple cipher that translates number to series of  <strong>.</strong> <strong>(</strong> <strong>)</strong></p>
  
  <p>In order to <em>encrypt</em> a number (0 .. 2147483647) to this representation, I (think I) need:</p>
  
  <ul>
  <li>prime factorization</li>
  <li>for given <em>p</em> (<em>p</em> is Prime), order sequence of p (ie. <strong>PrimeOrd(2)</strong> == <strong>0</strong>, <strong>PrimeOrd(227)</strong> == <strong>49</strong>)  </li>
  </ul>
  
  <h3>Some examples</h3>
  
  <pre>
      0   .                  6    (()())
      1   ()                 7    (...())
      2   (())               8    ((.()))
      3   (.())              9    (.(()))
      4   ((()))            10    (().())
      5   (..())            11    (....())
      227 (................................................())
      2147483648    ((..........()))
  </pre>
  
  <h3>My source code for the problem</h3>
  
  <pre><code>
  using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  using System.IO;
  
  static class P
  {
      static List&lt;int> _list = new List&lt;int>();
  
      public static int Nth(int n)
      {
          if (_list.Count == 0 || _list.Count &lt; n)
              Primes().Take(n + 1);
  
          return _list[n];
      }
  
      public static int PrimeOrd(int prime)
      {
          if (_list.Count == 0 || _list.Last() &lt; prime)
              Primes().First(p => p >= prime);
  
          return (_list.Contains(prime)) ? _list.FindIndex(p => p == prime) : -1;
      }
  
      public static List&lt;int> Factor(int N)
      {
          List&lt;int> ret = new List&lt;int>();
          for (int i = 2; i &le; N; i++)
              while (N % i == 0)
              {
                  N /= i;
                  ret.Add(i);
              }
  
          return ret;
      }
  
      public static IEnumerable&lt;int> Primes()
      {
          _list = new List&lt;int>();
  
          _list.Add(2);
          yield return 2;
  
          Func&lt;int, bool> IsPrime = n => _list.TakeWhile(p => p &le; (int)Math.Sqrt(n)).FirstOrDefault(p => n % p == 0) == 0;
  
          for (int i = 3; i &lt; Int32.MaxValue; i += 2)
          {
              if (IsPrime(i))
              {
                  _list.Add(i);
                  yield return i;
              }
          }
      }
  
      public static string Convert(int n)
      {
          if (n == 0) return ".";
          if (n == 1) return "()";
  
          StringBuilder sb = new StringBuilder();
          var p = Factor(n);
          var max = PrimeOrd(p.Last());
          for (int i = 0; i &le; max; i++)
          {
              var power = p.FindAll((x) => x == Nth(i)).Count;
              sb.Append(Convert(power));
          }
          return "(" + sb.ToString() + ")";
      }
  }
  
  class Program
  {
      static void Main(string[] args)
      {
          string line = Console.ReadLine();
          try
          {
              int num = int.Parse(line);
              Console.WriteLine("{0}: '{1}'", num, P.Convert(num));
          }
          catch
          {
              Console.WriteLine("You didn't entered number!");
          }
      }
  }
  </code></pre>
  
  <p><strong>The problem is SLOWNESS of procedure PrimeOrd. Do you know some FASTER solution for finding out order of prime in primes?</strong></p>
  
  <h2>Heading</h2>
  
  <h3>If You know how to speed-up finding order of prime number, please, suggest something.  :-)</h3>
  
  <h2>Thank You.</h2>
  
  <hr>
  
  <p>P.S. The biggest prime less than 2,147,483,648 is <strong>2,147,483,647</strong> and it's <strong>105,097,565th</strong> prime. There is no need to expect bigger number than 2^31.</p>