c# - 第 n 个素数问题，需要加快速度

Question

有一个简单的密码可以将数字转换为 系列。 ( )

为了加密一个数字(0 .. 2147483647)到这个表示，我(认为我)需要:

• 质因数分解
• 对于给定的 p(p 是质数)，p 的顺序序列(即。PrimeOrd(2) == 0 , PrimeOrd(227) == 49)

一些例子

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

My source code for the problem

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 更大的数字。

Answer 1

这不是您应该在运行时做的事情。更好的选择是预先计算所有这些素数，然后以某种方式将它们放入您的程序中(静态数组，或要读入的文件)。缓慢的代码然后作为开发过程的一部分运行(无论如何都很慢 :-)，不在您需要速度的地方。

那么这只是某种查找的问题，而不是每次需要时都计算它们。