Was macht dieser Vektor-Array-Code? (C++)

Question

Schwierigkeiten dabei, eine Erklärung dafür zu finden.

Was macht dieser Code? Ich verstehe, dass es eine Reihe von Vektor erzeugt, aber das ist es. Wie kann ich das Vektor-Array drucken und auf Elemente zugreifen, um damit zu experimentieren?

#define MAXN 300009 
vector<int>dv[MAXN]; 
int main() 
{ 
    for(int i=1;i<MAXN;i++) 
    for(int j=i;j<MAXN;j+=i) 
     dv[j].push_back(i); 
} 

Answer 1

Der Code ist einfach genug zu instrumentieren. Die Realität dessen, was es produziert, ist eine sehr einfache (und sehr ineffiziente) Sieve of Eratosthenes. Wenn Sie diesen Algorithmus verstehen, werden Sie sehen, was dieser Code bewirkt, um das zu erzeugen.

Edit: Es ist auch ein Faktor-Tabellengenerator. Siehe Bearbeiten unten.

Den Code und Dumping-Ausgabe nachinstrumentieren und reduzieren die Anzahl der Schleifen zur Vereinfachung haben wir so etwas wie der folgende Code. Wir verwenden range-based-for Schlaufen in der Anordnung von Vektoren über jeden Vektor Aufzählen:

#include <iostream> 
#include <vector> 

#define MAXN 20 
std::vector<int>dv[MAXN]; 

int main() 
{ 
    for(int i=1;i<MAXN;i++) 
    { 
     for(int j=i;j<MAXN;j+=i) 
      dv[j].push_back(i); 
    } 

    for (auto const& v : dv) 
    { 
     for (auto x : v) 
      std::cout << x << ' '; 
     std::cout << '\n'; 
    } 
} 

Die resultierende Ausgabe ist:

1 
1 2 
1 3 
1 2 4 
1 5 
1 2 3 6 
1 7 
1 2 4 8 
1 3 9 
1 2 5 10 
1 11 
1 2 3 4 6 12 
1 13 
1 2 7 14 
1 3 5 15 
1 2 4 8 16 
1 17 
1 2 3 6 9 18 
1 19 

Nun beachten jeden Vektor, der nur zwei Elemente (1 und eine zusätzliche Nummer). Diese zweite Nummer ist prime. In unserem Testfall diese beiden Elementvektoren sind:

1 2 
1 3 
1 5 
1 7 
1 11 
1 13 
1 17 
1 19 

Kurz gesagt, dies ist ein sehr einfach ist, und unglaublich ineffizient Primzahlen zu finden. Eine geringfügige Änderung in den Ausgangsschleifen, um nur das zweite Element aller Vektoren der Länge-nur-zwei auszugeben, wird daher alle Primzahlen erzeugen, die niedriger als MAXN sind. Daher verwenden:

for (auto const& v : dv) 
{ 
    if (v.size() == 2) 
     std::cout << v[1] << '\n'; 
} 

Wir werden alle Primzahlen von [2...MAXN)

---

bearbeiten erhalten: Faktor Tabellengenerierung

Wenn es nicht offensichtlich ist, hat jeder Vektor ein End-Element (Das stimmt nicht zufällig mit den Indizes des äußeren Arrays überein. Alle vorhergehenden Elemente bilden die positiven Faktoren dieser Zahl. Zum Beispiel:

1 2 5 10 

ist der dv[10] Vektor, und sagen Sie 10 Faktoren 1,2,5,10 haben. Ebenso ist

1 2 3 6 9 18 

der dv[18] Vektor, und sagen Sie, 18 Faktoren haben 1,2,3,6,9,18.

Kurz gesagt, wenn jemand alle Faktoren einer gewissen Anzahl N, die die Umsetzung all diese Informationen in tabellarische Form < MAXN, dies wäre ein Weg, um wissen wollte.