有一个简单的密码可以将数字转换为 系列。 ( )
为了加密一个数字(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 更大的数字。
最佳答案
这不是您应该在运行时做的事情。更好的选择是预先计算所有这些素数,然后以某种方式将它们放入您的程序中(静态数组,或要读入的文件)。缓慢的代码然后作为开发过程的一部分运行(无论如何都很慢 :-),不在您需要速度的地方。
那么这只是某种查找的问题,而不是每次需要时都计算它们。
关于c# - 第 n 个素数问题,需要加快速度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/929712/