проблема с n-м простым числом, нужно немного ускорить ее
https://stackoverflow.com/questions/929712
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Существует простой шифр, который переводит число в серию . ( )
Для того, чтобы шифровать число (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.Знаете ли вы какое-нибудь БОЛЕЕ БЫСТРОЕ решение для определения порядка следования простых чисел в простых числах?
Заголовок
Если Вы знаете, как ускорить нахождение порядка следования простых чисел, пожалуйста, предложите что-нибудь.:-)
Спасибо.
P.S.Самое большое простое число , меньшее 2,147,483,648 , равно 2,147,483,647 и это 105,097,565 тыс. первичный.Нет необходимости ожидать большего числа, чем 2 ^ 31.
Решение
Вы должны кэшировать простые числа в _list, а затем использовать его как для Factor, так и для PrimeOrd.Кроме того, избегайте операторов LINQ, таких как takeWhile, которые создают значения, которые вы выбрасываете.
Вот оптимизированная версия:
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=сайт%3Astackoverflow.com+простое число иbtnG=Поиск
Забавное вычисление простых чисел
Как я могу найти простые числа с помощью битовых операций в C ++?
Программа для работы с простыми числами
Если вам нужен список известных простых чисел, взгляните здесь
