Nth problem with a simple number, you need to speed it up a bit

Question

There is a simple cipher that translates a number in a row . ( )

To encrypt the number (0 .. 2147483647) to this view, I (I think) need:

• simple factorization
• for a given p (p - Prime), the sequence of orders p (i.e. PrimeOrd (2) == 0 , PrimeOrd (227) == 49 )

Some examples

    0. 6 (() ())
    1 () 7 (... ())
    2 (()) 8 ((. ()))
    3 (. ()) 9 (. (()))
    4 ((())) 10 ((). ())
    5 (.. ()) 11 (.... ())
    227 (................................................ ())
    2147483648 ((.......... ()))

My problem source code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

static class P
{
    static List<int> _list = new List<int>();

    public static int Nth(int n)
    {
        if (_list.Count == 0 || _list.Count < n)
            Primes().Take(n + 1);

        return _list[n];
    }

    public static int PrimeOrd(int prime)
    {
        if (_list.Count == 0 || _list.Last() < prime)
            Primes().First(p => p >= prime);

        return (_list.Contains(prime)) ? _list.FindIndex(p => p == prime) : -1;
    }

    public static List<int> Factor(int N)
    {
        List<int> ret = new List<int>();
        for (int i = 2; i ≤ N; i++)
            while (N % i == 0)
            {
                N /= i;
                ret.Add(i);
            }

        return ret;
    }

    public static IEnumerable<int> Primes()
    {
        _list = new List<int>();

        _list.Add(2);
        yield return 2;

        Func<int, bool> IsPrime = n => _list.TakeWhile(p => p ≤ (int)Math.Sqrt(n)).FirstOrDefault(p => n % p == 0) == 0;

        for (int i = 3; i < 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 ≤ 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!");
        }
    }
}

Problem SLOWNESS procedures PrimeOrd. Do you know any FASTER solution for determining the order of primes in primes?

Headline

If you know how to speed up your prime order search, please suggest something. :-)

Thanks.

---

PS The largest stroke is less than 2 147 483 648, 2 147 483 647 and 105 097 565 prime. There is no need to expect more than 2 ^ 31.

Answer 1

_list, Factor, PrimeOrd. , LINQ, TakeWhile, , .

:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

static class P
{
    private static List<int> _list = new List<int>();

    public static int Nth(int n)
    {
        if (_list.Count == 0 || _list.Count <= n)
        {
            GenerateNextPrimes().First(p => _list.Count >= n);            
        }

        return _list[n];
    }

    public static int PrimeOrd(int prime)
    {
        var primes = GrowPrimesTo(prime);
        return primes.IndexOf(prime);
    }

    public static List<int> Factor(int N)
    {
        List<int> ret = new List<int>();        
        GrowPrimesTo(N);

        for (int ixDivisor = 0; ixDivisor < _list.Count; ixDivisor++)
        {
            int currentDivisor = _list[ixDivisor];

            while (N % currentDivisor == 0)
            {
                N /= currentDivisor;
                ret.Add(currentDivisor);
            }

            if (N <= 1)
            {
                break;
            }
        }

        return ret;
    }

    private static List<int> GrowPrimesTo(int max)
    {
        if (_list.LastOrDefault() >= max)
        {
            return _list;
        }

        GenerateNextPrimes().First(prime => prime >= max);
        return _list;        
    }

    private static IEnumerable<int> GenerateNextPrimes()
    {
        if (_list.Count == 0)
        {
            _list.Add(2);
            yield return 2;
        }

        Func<int, bool> IsPrime =
            n =>
            {
                // cache upperBound
                int upperBound = (int)Math.Sqrt(n);
                for (int ixPrime = 0; ixPrime < _list.Count; ixPrime++)
                {
                    int currentDivisor = _list[ixPrime];
                    if (currentDivisor > upperBound)
                    {
                        return true;
                    }

                    if ((n % currentDivisor) == 0)
                    {
                        return false;
                    }
                }

                return true;
            };

        // Always start on next odd number
        int startNum = _list.Count == 1 ? 3 : _list[_list.Count - 1] + 2;
        for (int i = startNum; i < 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 <= 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();
        int num;

        if(int.TryParse(line, out num))
        {   
            Console.WriteLine("{0}: '{1}'", num, P.Convert(num));             
        }
        else
        {
            Console.WriteLine("You didn't entered number!");
        }
    }
}

Answer 2

, . - , ( ). ( :-), , .

- , , .

Answer 3

. SO:

http://www.google.com/search?q=site%3Astackoverflow.com+prime+number&btnG=Search

(: ?)

++?

#

,