komplizierter JavaScript

[Dommie]

Hallo,

entschuldigt, wenn ich Euch da sowas kompliziertes abverlange - vielleicht ist es auch gar nicht so kompliziert, sondern mein Köpfchen blickt das wieder nicht:

habe folgenden JavaScript gefunden:

//return array of all primes less than integer n
function findPrimes(n) {
  var i,s,p,ans;
  s=new Array(n);
  for (i=0;i<n;i++)
    s[i]=0;
  s[0]=2;
  p=0;    //first p elements of s are primes, the rest are a sieve
  for(;s[p]<n;) {                  //s[p] is the pth prime
    for(i=s[p]*s[p]; i<n; i+=s[p]) //mark multiples of s[p]
      s[i]=1;
    p++;
    s[p]=s[p-1]+1;
    for(; s[p]<n && s[s[p]]; s[p]++); //find next prime (where s[p]==0)
  }
  ans=new Array(p);
  for(i=0;i<p;i++)
    ans[i]=s[i];
  return ans;
}

Könntet Ihr, wenn's beliebt auch per eMail, mir bitte erklären, wie jetzt dieser Script funktioniert? Einiges habe ich mittlerweile selbst herausgefunden, mögen es auch nur die einfacheren arithmetischen Funktionen sein.

Auch wenn es etwas Zeit kosten sollte, für Eure Antworten danke ich Euch schon mal - ich sitz da schon stundenlang dran...

Euer Dommie...

[Vinzenz Mai]

Hallo Dommie,

das Skript sieht nach dem Sieb des Eratosthenes aus.

Könntet Ihr, wenn's beliebt auch per eMail,

nein, das beliebt mir nicht.

mir bitte erklären, wie jetzt dieser Script funktioniert? Einiges habe ich mittlerweile selbst herausgefunden, mögen es auch nur die einfacheren arithmetischen Funktionen sein.

Schau' Dir bitte den verlinkten Wikipediaartikel an. Wenn Du Javascript lernen willst, so empfehle ich Dir das Javascript-Kapitel von SELFHTML.

Freundliche Grüße

Vinzenz

[Gunnar Bittersmann]

Hello out there!

Durch

findPrimes

und

sieve

hättest du drauf kommen können, was das Script nach welchem Algorithmus  macht.

   p=0;  
   for(;s[p]<n;) {  
     foo();  
     p++;  
     bar();  
   }

Wer schreibt denn sowas?

Außerdem läuft die Schleife viel zu lange; bei Math.sqrt(n) kann schon aufgehört werden.

Wenn du das mit „kompliziert“ meintest – die Implementierung ist in der Tat grottig.

See ya up the road,
Gunnar

[Gunnar Bittersmann]

Hello out there!

die Implementierung ist in der Tat grottig.

Eine vernünftige[tm] sieht so aus:

  
// primesArray(n)  
// gibt ein Array von booleschen Werten zurück  
// an i-ter Stelle steht true, wenn i prim ist; sonst false  
function primesArray(n) {  
  var sqrt_n = Math.sqrt(n);  
  var a = new Array(n);  
  for (var i = 2; i < n; i++)  
    a[i] = true;  
  for (var i = 2; i < sqrt_n; i++)  
    if (a[i])  
      for (var j = i * i; j < n; j += i)  
        a[j] = false;  
  return a;  
}  
  
// primesList(n)  
// gibt eine Liste der Primzahlen kleiner als n zurück  
function primesList(n) {  
  var l = new Array();  
  var a = primesArray(n);  
  for (var i = 2; i < n; i++)  
    if (a[i])  
      l.push(i);  
  return l;  
}  

See ya up the road,
Gunnar