n-th number number، تحتاج إلى تسريع ذلك قليلا

Question

هناك تشفير بسيط يترجم الرقم إلى سلسلة . ( )

بغرض تشفير رقم (0 .. 2147483647) لهذا التمثيل، أنا (أعتقد أنني) بحاجة إلى:

• العوامل الرئيسية
• لأنه معين ب (ب هو رئيس الوزراء)، طلب تسلسل P (أي. بدوردورد (2) == 0, بدوردورد (227) == 49)

بعض الأمثلة

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

شفرة المصدر الخاصة بي للمشكلة

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!");
        }
    }
}

المشكلة هي البطء من Primetord. هل تعرف بعض الحل الأسرع لمعرفة ترتيب رئيس الوزراء في الأعداد الأولية؟

عنوان

إذا كنت تعرف كيفية تسريع العثور على ترتيب الرقم الأول، من فضلك، اقترح شيئا. :-)

شكرا.

---

ملاحظة: أكبر رئيسي أقل من 2،147،483،648 2,147,483,647 وانها 105،097،565th رئيس الوزراء. ليست هناك حاجة لتوقع عدد أكبر من 2 ^ 31.

Answer 1

يجب عليك التخزين المؤقت للعميل الأولية إلى _List ثم استخدامه لكل من العامل والمواد. بالإضافة إلى ذلك تجنب المشغلين من مشغلي LINQ مثل الأخشاب التي تخلق القيم التي تتخلص منها.

إليك نسخة محسنة:

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

يرجى الاطلاع على الأسئلة:

http://www.google.com/search؟q=site٪3astackoverflow.com+prime+number&btng=search.

العثور على أرقام رئيسية مع غربال eratosthenes (في الأصل: هل هناك طريقة أفضل لإعداد هذه الصفيف؟)

حساب رقم العرض المرح

كيف يمكنني العثور على أرقام رئيسية من خلال عمليات بت في C ++؟

أرقام رئيس C #

العثور على أرقام مركبة

برامج الأعداد الأولية

إذا كنت بحاجة إلى قائمة من الأعداد الأولية المعروفة، فابحث عن نظرة هنا