Gib alle Primzahlen zurück, die kleiner als M sind
Gegeben eine ganze Zahl M. gebe alle Primzahlen kleiner als M zurück.
Geben Sie einen Algorithmus so gut wie Sie können. Sie müssen die Komplexität von Zeit und Raum berücksichtigen.
Jeder kann durchkommen? Schätze!
9 Antworten
Ein paar zusätzliche Leistungshinweise:
- Sie müssen nur bis zur Quadratwurzel von
ntesten, da jede zusammengesetzte Zahl mindestens einen Primfaktor kleiner oder gleich der Quadratwurzel hat
- Sie können bekannte Primzahlen zwischenspeichern, während Sie sie erzeugen, und nachfolgende Zahlen gegen nur die Zahlen in dieser Liste testen (statt jeder Zahl unter
sqrt(n)) - Sie können natürlich gerade Zahlen überspringen
π (n) zählen die Primzahlen kleiner oder gleich n. Pafnuty Chebyshev hat gezeigt, dass wenn
lim n → ∞ π (n) / (n / ln (n))
existiert, es ist 1. Es gibt viele Werte, die ungefähr gleich π (n) sind, wie in der Tabelle gezeigt.
Es gibt die richtige Zahl der Primzahl für dieses Zahlenformat. Ich hoffe, das wird hilfreich sein.
Die übliche Antwort besteht darin, das Sieve von Eratosthenes , aber das ist wirklich nur eine Lösung, um die Liste aller Primzahlen kleiner als N zu finden. Wenn Sie Privalitätstests für bestimmte Nummern, es gibt bessere Möglichkeiten für große Zahlen.
Ich bin ein Anfänger Programmierer in c # (und neu in S. O.), so dass dies ein wenig wortreich sein kann. trotzdem habe ich das getestet und ich arbeite.
das ist, was ich mir ausgedacht habe:
%Vor%Sie können dies tun, indem Sie eine dynamische Programmierung mit dem Bottom-Up-Prinzip, das Sieb von Eratosthenes, verwenden Im Grunde erstellen Sie einen booleschen Cache aller Zahlen bis n und Sie markieren jeweils die Vielfachen jeder Zahl als not_prime. Weitere Optimierungen können erzielt werden, indem nur bis zu sqrt (n) geprüft wird, da jede zusammengesetzte Zahl mindestens einen Teiler weniger als sqrt (n)
aufweist %Vor%Das Sieve von Atkin ist auch der beste Algorithmus, der in diesem Fall implementiert wird und nur O (N) -Operationen und O (N) -Raum benötigt. Eine detaillierte Erklärung des Algorithmus und des Pseudocodes finden Sie in Ссылка .