Wie kann ich mein Akka-Streams Prime-Sieb ändern, um Modulo-Checks für bekannte Primzahlen auszuschließen?

Question

Ich schrieb ein Sieb mit akka Strömen prime Mitglieder einer beliebigen Quelle Int zu finden:

object Sieve extends App { 

    implicit val system = ActorSystem() 
    implicit val mat = ActorMaterializer(ActorMaterializerSettings(system)) 
    implicit val ctx = implicitly[ExecutionContext](system.dispatcher) 

    val NaturalNumbers = Source.fromIterator(() => Iterator.from(2)) 

    val IsPrimeByEurithmethes: Flow[Int, Int, _] = Flow[Int].filter { 
    case n: Int => 
     (2 to Math.floor(Math.sqrt(n)).toInt).par.forall(n % _ != 0) 
    } 

    NaturalNumbers.via(IsPrimeByEurithmethes).throttle(100000, 1 second, 100000, ThrottleMode.Shaping).to(Sink.foreach(println)).run() 
} 

Ok, so scheint dies anständig gut zu funktionieren. Allerdings gibt es zumindest einige potenzielle Problembereiche:

1. Die Modulo-Prüfungen werden ausgeführt unter Verwendung von par.forall, dh sie sind innerhalb der Flow dass filter s völlig versteckt sind, aber ich kann sehen, wie es sinnvoll wäre, zu haben a Map von der candidate n zu einer anderen Map von jeder n % _. Könnte sein.
2. Ich überprüfe viel zu viele der Kandidaten unnötig - sowohl in Bezug auf die Überprüfung n, dass ich bereits wissen, sind nicht Prime auf der Grundlage der vorherigen Ergebnisse, und durch Überprüfung n % _, die redundant sind. Tatsächlich, selbst wenn ich denke, dass die n Primzahl ist, reicht es aus, nur die bekannten Primzahlen bis zu diesem Punkt zu überprüfen.

Der zweite Punkt ist meine unmittelbare Sorge.

Ich denke, dass ich ziemlich leicht beweisen kann, dass es einen effizienteren Weg gibt - indem man den source herausfiltert, der jedem NEUEN Strich gegeben wird. So

dann ....

2, 3, 4, 5, 6, 7, 8, 9, 10, 11... => (after finding p=2) 

2, 3, 5, 7, 9, , 11... => (after finding p=3) 

2, 3, 5, 7,   , 11... => ... 

Jetzt, nach einem p und Filtern der Quelle zu finden, müssen wir wissen, ob der nächste Kandidat ein p ist. Nun, wir können sicher sagen, dass es eine Primzahl ist, wenn der größte bekannte Primzahl größer als seine Wurzel ist, was immer passiert, ich glaube, so genügt es, nur das nächste Element zu holen ...

2, 3, 4, 5, 6, 7, 8, 9, 10, 11... => (after finding p=2) PICK n(2) = 3 

2, 3, 5, 7, 9, , 11... => (after finding p=3) PICK n(3) = 5 

2, 3, 5, 7,   , 11... => (after finding p=5) PICK n(5) = 7 

Dies scheint darauf hinzu Ich mag es, das ursprünglich bereitgestellte Sieb neu zu schreiben, um weit weniger Kontrollen zu machen, die auf Kosten einer strengen sequenziellen Abhängigkeit gehen.

Eine weitere Idee - ich konnte die Einschränkung entfernen, indem Sie Dinge in Bezug auf die Symbole, wie das Mindestangebot an Modulo Kontrollen arbeiten, die Primalität erforderlich machen, usw.

Bin ich den Holzweg? Wenn nicht, wie kann ich auf diese Weise mit meiner Quelle herumspielen?

Answer 1

Ich habe gerade angefangen, mit Akka-Streams herumzuspielen, also könnte es bessere Lösungen als diese geben (besonders weil der Code sich irgendwie plump anfühlt) - aber Ihr zweiter Punkt schien mir die richtige Herausforderung zu sein Aufbau einer Rückkopplungsschleife innerhalb von Akka-Streams.

finden meine volle Lösung hier: https://gist.github.com/MartinHH/de62b3b081ccfee4ae7320298edd81ee

Die Hauptidee der Primzahlen zu akkumulieren war, die bereits gefunden und sie mit dem Strom der eingehenden natürlichen Zahlen verschmelzen, so dass die Primzahlen-Check auf der Grundlage der Ergebnisse durchgeführt werden könnte zu N wie folgt:

def isPrime(n: Int, primesSoFar: SortedSet[Int]): Boolean = 
    !primesSoFar.exists(n % _ == 0) && 
    !(primesSoFar.lastOption.getOrElse(2) to Math.floor(Math.sqrt(n)).toInt).par.exists(n % _ == 0)