n-ième problème des nombres premiers, ont besoin d'accélérer un peu
https://stackoverflow.com/questions/929712
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Il est de chiffrement simple qui se traduit par nombre à une série de . ( )
Pour Chiffrer un numéro (0 .. 2147483647) à cette représentation, je (crois que je) besoin:
- factorisation
- for donné p ( p est le premier), la séquence de commande de p (p. PrimeOrd (2) == 0 , PrimeOrd (227) == 49 )
Quelques exemples
0 . 6 (()())
1 () 7 (...())
2 (()) 8 ((.()))
3 (.()) 9 (.(()))
4 ((())) 10 (().())
5 (..()) 11 (....())
227 (................................................())
2147483648 ((..........()))
Mon code source du problème
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!");
}
}
}
Le problème est Lenteur de procédure PrimeOrd. Connaissez-vous une solution plus rapide pour savoir l'ordre de choix dans les nombres premiers?
Rubrique
Si vous savez comment trouver accélérer l'ordre du nombre premier, s'il vous plaît, suggérer quelque chose. : -)
Merci.
P.S. Le plus grand taux préférentiel moins de 2.147.483.648 est 2147483647 et il est 105097565e prime. Il n'y a pas besoin d'attendre plus grand nombre de 2 ^ 31.
La solution
Vous devez mettre en cache les nombres premiers à _list et ensuite l'utiliser pour les facteurs et PrimeOrd. En outre éviter les opérateurs opérateurs de LINQ comme TakeWhile qui créent des valeurs que vous jeter.
Voici une version optimisée:
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!");
}
}
}
Autres conseils
Ce n'est pas quelque chose que vous devriez faire au moment de l'exécution. Une meilleure option est de pré-calculer tous ces nombres premiers, puis les mettre dans votre programme en quelque sorte (un tableau statique, ou un fichier à lire dans). Le code lent est alors exécuté dans le cadre du processus de développement (ce qui est lent de toute façon :-), pas au point où vous avez besoin de votre vitesse.
Ensuite, il est juste une question d'une recherche d'une sorte plutôt que de les calculer à chaque fois que vous en avez besoin.
S'il vous plaît voir SO questions:
http://www.google.com /search?q=site%3Astackoverflow.com+prime+number&btnG=Search
calcul des nombres premiers amusant
Comment puis-je trouver des nombres premiers par opérations de bits en C ++?
Si vous avez besoin d'une liste de nombres premiers connus, consultez ici
