JavaScript-Programm zum Zählen von Primzahlen in einem Bereich

Eine Primzahl ist eine Zahl, die genau zwei perfekte Teiler hat. Wir werden zwei Möglichkeiten sehen, die Anzahl der Primzahlen in einem bestimmten Bereich zu ermitteln. Die erste besteht darin, eine Brute-Force-Methode zu verwenden, die eine recht hohe zeitliche Komplexität aufweist. Anschließend werden wir diese Methode verbessern und den Sieve of Eratosthenes-Algorithmus übernehmen, um eine bessere Zeitkomplexität zu erreichen. In diesem Artikel ermitteln wir mithilfe der Programmiersprache JavaScript die Gesamtzahl der Primzahlen in einem bestimmten Bereich.

Gewaltgesetz

Zunächst lernen wir mit dieser Methode, wie wir herausfinden, ob eine Zahl eine Primzahl ist oder nicht. Wir können sie auf zwei Arten herausfinden. Eine Methode hat die Zeitkomplexität O(N) und die andere Methode hat die Zeitkomplexität O(sqrt(N)).

Direkte Methode zur Bestimmung, ob eine Zahl eine Primzahl ist

Beispiel

Zuerst führen wir eine for-Schleife durch, bis wir eine Zahl erhalten, und zählen die Zahlen, die die Zahl teilen können. Wenn die Zahl, die die Zahl teilen kann, nicht gleich 2 ist, ist die Zahl keine Primzahl, andernfalls die Zahl ist eine Primzahl. Schauen wir uns den Code an -

function isPrime(number){
   var count = 0;
   for(var i = 1;i<=number;i++)    {
      if(number%i == 0){
         count = count + 1;
      }
   }
   if(count == 2){
      return true;
   }
   else{
      return false;
   }
}

// checking if 13 and 14 are prime numbers or not 
if(isPrime(13)){
   console.log("13 is the Prime number");
}
else{    
   console.log("13 is not a Prime number")
}

if(isPrime(14)){
   console.log("14 is the Prime number");
}
else{
   console.log("14 is not a Prime number")
}

Im obigen Code gehen wir von 1 zu Zahl, suchen die Zahl im Zahlenbereich, die die gegebene Zahl teilen kann, ermitteln, wie viele Zahlen die gegebene Zahl teilen können, und drucken das Ergebnis darauf basierend aus.

Die zeitliche Komplexität des obigen Codes beträgt O(N). Die Prüfung, ob jede Zahl eine Primzahl ist, kostet O(N*N), was bedeutet, dass dies keine gute Möglichkeit zur Überprüfung ist.

Mathematische Methoden

Wir wissen, dass der Quotient auch eine vollkommene ganze Zahl ist, wenn eine Zahl eine andere Zahl vollständig teilt. Das heißt, wenn eine Zahl p durch eine Zahl q geteilt werden kann, ist der Quotient r, also q * r = p. r dividiert auch die Zahl p durch den Quotienten q. Das bedeutet also, dass perfekte Teiler immer paarweise vorkommen.

Beispiel

Aus der obigen Diskussion können wir schließen, dass wir in sehr kurzer Zeit das gleiche Ergebnis erhalten, wenn wir nur die Division durch die Quadratwurzel von N überprüfen. Sehen wir uns den Code der obigen Methode an -

function isPrime(number){
   if(number == 1) return false
   var count = 0;
   for(var i = 1;i*i<=number;i++){
      if(number%i == 0){
         count = count + 2;
      }
   }
   if(count == 2){
      return true;
   }
   else{
      return false;
   }
}
// checking if 67 and 99 are prime numbers or not 
if(isPrime(67)){
   console.log("67 is the Prime number");
}
else{
   console.log("67 is not a Prime number")
}
if(isPrime(99)){
   console.log("99 is the Prime number");
}
else{
   console.log("99 is not a Prime number")
}

Im obigen Code haben wir gerade den vorherigen Code geändert, indem wir den Umfang der for-Schleife geändert haben, da jetzt nur noch die erste Quadratwurzel von N Elementen überprüft wird, und wir haben die Anzahl um 2 erhöht.

Die zeitliche Komplexität des obigen Codes beträgt O(sqrt(N)), was besser ist, was bedeutet, dass wir diese Methode verwenden können, um die Anzahl der Primzahlen zu ermitteln, die in einem bestimmten Bereich vorhanden sind.

Die Anzahl der Primzahlen im Bereich von L bis R

Beispiel

Wir werden den zuvor angegebenen Code in einem Bereich implementieren und die Anzahl der Primzahlen in einem bestimmten Bereich zählen. Lassen Sie uns den Code implementieren -

function isPrime(number){
   if(number == 1) return false
   var count = 0;
   for(var i = 1;i*i<=number;i++)    {
      if(number%i == 0){
         count = count + 2;
      }
   }
   if(count == 2){
      return true;
   }
   else{
      return false;
   }
}
var L = 10
var R = 5000
var count = 0
for(var i = L; i <= R; i++){
   if(isPrime(i)){
      count = count + 1;
   }
}
console.log(" The number of Prime Numbers in the given Range is: " + count);

Im obigen Code iterieren wir mit einer for-Schleife über den Bereich von L bis R und prüfen bei jeder Iteration, ob die aktuelle Zahl eine Primzahl ist. Wenn die Zahl eine Primzahl ist, erhöhen wir die Zahl und geben schließlich den Wert aus.

Die zeitliche Komplexität des obigen Codes beträgt O(N*N), wobei N die Anzahl der Elemente im Bereich ist.

Eratosthenes-Algorithmus-Screening

Beispiel

Der Sieve of Eratosthenes-Algorithmus arbeitet sehr effizient und kann die Anzahl der Primzahlen in einem bestimmten Bereich in O(Nlog(log(N)))-Zeit ermitteln, was im Vergleich zu anderen Algorithmen sehr schnell ist. Das Sieb nimmt O(N)-Raum ein, aber das spielt keine Rolle, da die Zeit sehr effizient ist. Schauen wir uns den Code an und fahren dann mit der Erklärung des Codes fort -

var L = 10
var R = 5000
var arr = Array.apply(null, Array(R+1)).map(Number.prototype.valueOf,1);
arr[0] = 0
arr[1] = 0

for(var i = 2;i<=R;i++){
   if(arr[i] == 0){
      continue;
   }
   for(var j = 2; i*j <= R; j++){
      arr[i*j] = 0;
   }
}

var pre = Array.apply(null, Array(R+1)).map(Number.prototype.valueOf,0);
for(var i = 1; i<= R;i++){
   pre[i] = pre[i-1] + arr[i];
}
answer = pre[R]-pre[L-1]
console.log("The number of Prime Numbers in the given Range is: " + answer);

Im obigen Code sehen wir die Implementierung des Siebes des Eratosthenes. Zuerst haben wir ein Array mit der Größe R erstellt und anschließend mit der for-Schleife durch das Array iteriert. Wenn die aktuelle Zahl für jede Iteration nicht 1 ist, bedeutet dies, dass sie keine Primzahl ist, andernfalls ist sie eine Primzahl und wir haben alle Zahlen, die kleiner als R sind Vielfache der aktuellen Primzahl werden entfernt. Anschließend erstellen wir ein Präfix-Array, das die Primzahl von 0 bis zum aktuellen Index speichert und in konstanter Zeit eine Antwort auf jede Abfrage im Bereich 0 bis R liefern kann.

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N*log(log(N))), was im Vergleich zu O(N*N) und O(N*(sqrt(N))) viel besser ist. Im Vergleich zum vorherigen Code weist der obige Code eine höhere Raumkomplexität von O(N) auf.

Fazit

In diesem Tutorial haben wir gelernt, wie man mithilfe der Programmiersprache JavaScript die Anzahl der Primzahlen in einem bestimmten Bereich ermittelt. Eine Primzahl ist eine Zahl, die genau zwei perfekte Teiler hat. 1 ist keine Primzahl, da sie nur einen perfekten Teiler hat. Wir haben drei Methoden mit der Zeitkomplexität O(N*N), O(N*sqrt(N)) und O(N*log(log(N))) gesehen. Darüber hinaus beträgt die räumliche Komplexität der ersten beiden Methoden O(1) und die räumliche Komplexität der Sieve of Eratosthenes-Methode beträgt O(N).

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Zählen von Primzahlen in einem Bereich. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!