n番目の素数の問題、少しスピードを上げる必要があります

https://stackoverflow.com/questions/929712

06-09-2019
|

質問

数値を一連の文字列に変換する単純な暗号があります。 . ( )

するために 暗号化する 数値 (0 ..2147483647) この表現に対して、私は次のことが必要であると考えています。

素因数分解
与えられたもの p (p は素数）、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!");
        }
    }
}

問題はプロシージャ PrimeOrd の遅さです。素数の順序を見つけるためのより高速な解決策を知っていますか?

見出し

素数の順序を見つける時間を短縮する方法を知っている場合は、何か提案してください。:-)

ありがとう。

追伸2,147,483,648 未満の最大の素数は次のとおりです。 2,147,483,647 そしてそれは 105,097,565位 プライム。2^31 より大きな数値を期待する必要はありません。

解決

あなたは_List、その後ファクターとPrimeOrdの両方のためにそれを使用するために素数をキャッシュする必要があります。さらに、あなたは捨てる値を作成TakeWhileのような演算子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!");
        }
    }
}

他のヒント

これは、あなたが実行時にやるべきものではありません。より良いオプションは、これらすべての素数を事前に計算して、何とか自分のプログラムの中で（静的配列、または読み込まれるファイル）を入れることです。遅いコードを使用すると、あなたの速度を必要とする時点で:-)とにかく遅い開発プロセス（のないのの一部として実行している。

そして、それだけでいくつかの並べ替えの検索の問題ではなく、それらにあなたがそれらを必要とするたびに計算するのです。

SO質問をご参照くださいます：

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

素数を見つけますエラトステネスのふるいで（もともと：この配列を準備する良い方法はありますか？）する

プライム数計算楽しくする

私は経由素数を見つけることができます。

方法Cでのビット演算++ですか

素数C＃の

合成数に検索

素数プログラムの

あなたは、既知の素数のリストが必要な場合は、

、こちら

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow