Существует простой шифр, который переводит число в серию . ( )
Чтобы зашифровать число (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 ((..........()))
Мой исходный код проблемы
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. Знаете ли вы какое-то БЫСТРОЕ решение для определения порядка простых чисел в простых числах?
Заголовок
Если Вы знаете, как ускорить поиск порядка простого числа, пожалуйста, предложите что-нибудь. : -)
Спасибо.
P.S. Наибольшее простое число меньше 2 147 483 648 составляет 2 147 483 647 , а 105 097 565th простое. Нет необходимости ожидать большего числа, чем 2 ^ 31.