n-te Primzahl Problem, müssen sie beschleunigen ein bisschen
https://stackoverflow.com/questions/929712
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Es ist einfach Chiffre, die Nummer Reihe von übersetzt. ( )
Um encrypt eine Nummer (0 .. 2147483647) dieser Darstellung I (glaube ich) Notwendigkeit:
- Primfaktorzerlegung
- für gegebene p ( p ist Prime), um Folge von p (dh. PrimeOrd (2) == 0 , PrimeOrd (227) == 49 )
Einige Beispiele
0 . 6 (()())
1 () 7 (...())
2 (()) 8 ((.()))
3 (.()) 9 (.(()))
4 ((())) 10 (().())
5 (..()) 11 (....())
227 (................................................())
2147483648 ((..........()))
My Quellcode für das 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!");
}
}
}
Das Problem ist, Langsamkeit des Verfahrens PrimeOrd. Haben Sie eine schnellere Lösung kennen, um von vorrangiger in Primzahlen herauszufinden?
Überschrift
Wenn Sie wissen, wie zu beschleunigen Auftrag von Primzahlen zu finden, bitte, etwas vorschlagen. : -)
Danke.
P. S. Der größte Primzahl kleiner als 2147483648 ist 2147483647 und 105097565. prime. Es besteht keine Notwendigkeit größere Zahl als 2 ^ 31 zu erwarten.
Lösung
Sie sollten die Primzahlen Cache _list und es dann für beide verwenden Factor und PrimeOrd. Zusätzlich Betreiber LINQ-Operatoren wie Takewhile vermeiden, die Werte schaffen, die Sie wegwerfen.
Hier ist eine optimierte Version:
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!");
}
}
}
Andere Tipps
Das ist nicht etwas, das Sie während der Laufzeit tun sollen. Eine bessere Option ist, alle diese Primzahlen vorab zu berechnen und sie dann irgendwie in Ihrem Programm setzt (ein statisches Array oder eine Datei eingelesen werden). Der langsame Code wird dann als Teil des Entwicklungsprozesses läuft (was langsam sowieso :-), nicht an dem Punkt, wo Sie Ihre Geschwindigkeit benötigen.
Dann ist es nur eine Frage eines Nachschlag von einer Art, anstatt sie jedes Mal der Berechnung Sie sie benötigen.
Bitte beachten Sie SO Fragen:
http://www.google.com /search?q=site%3Astackoverflow.com+prime+number&btnG=Search
Wie kann ich Primzahlen durch Bit-Operationen in C ++?
Suche nach zusammengesetzten Zahlen
Wenn Sie eine Liste der bekannten Primzahlen benötigen, schauen Sie hier
