Suche nach composite numbers

Habe ich eine Reihe von Zufallszahlen. Die Reihe wird eigentlich bestimmt durch den Benutzer, sondern es werden bis zu 1000 zahlen. Sie befinden sich in:

vector<int> n

und die Werte eingefügt werden, wie diese:

srand(1);

for (i = 0; i < n; i++)
  v[i] = rand() % n;

Ich bin durch die Erstellung einer separaten Funktion zu finden, alle nicht-prime-Werte. Hier ist, was ich jetzt habe, aber ich weiß, es ist völlig falsch, wie bekomme ich prime und zusammengesetzte in der Serie.

void sieve(vector<int> v, int n)
{
  int i,j;

  for(i = 2; i <= n; i++)
     {
        cout << i << " % ";
        for(j = 0; j <= n; j++)
           {
              if(i % v[j] == 0)
                 cout << v[j] << endl;
           }
     }
}

Diese Methode in der Regel gearbeitet, wenn ich hatte gerade eine Reihe von zahlen von 0-1000, aber es scheint nicht zu funktionieren jetzt, wenn ich die zahlen nicht in Ordnung und Duplikate. Gibt es eine bessere Methode, um nicht-Primzahlen in einem Vektor? Ich bin in Versuchung, einfach erstellen Sie ein Vektor, füllen Sie es mit n zahlen und nur die nicht-Primzahlen, die Art und Weise, aber wäre das ineffizient?

Okay, da der Bereich von 0-1000 ich Frage mich, ob es einfacher, einfach erstellen Sie Vektor mit 0-n sortiert, und dann mit einem Sieb zu finden, die Primzahlen, ist dieser immer näher?

void sieve(vector<int> v, BST<int> t, int n)
{
  vector<int> v_nonPrime(n);
  int i,j;
  for(i = 2; i < n; i++)
      v_nonPrime[i] = i;

  for(i = 2; i < n; i++)
     {

        for(j = i + 1; j < n; j++)
           {
              if(v_nonPrime[i] % j == 0)
                 cout << v_nonPrime[i] << endl;
           }
     }
}

Ah, und es gibt eine schleichende Fehler drin. Sie sollten übergeben Sie den Vektor int als Referenz, sonst werden Sie nicht in der Lage sein, die Ergebnisse zu nutzen, die außerhalb des Siebes().
Auch Sie verwenden sollten, push_back und nicht v[i] = da der Vektor beginnt bei einer Größe von 0.
Ah, ich habe gerade gesehen, dass ich falsch verstanden, code: v wird nicht verwendet zum speichern der Ergebnisse, sondern um die Bereitstellung von input für die Methode. Immer noch eine Referenz speichert das programm vor dem kopieren v. size() Anzahl von Ganzzahlen, reservieren und freigeben.
nicht Primzahlen sind sogenannte composite-durch die Art und Weise

InformationsquelleAutor Doug | 2008-10-29

c++primes sieve

9

In diesem code:
```
if(i % v[j] == 0)
  cout << v[j] << endl;
```
Sind Sie testen Sie Ihre index um zu sehen, ob es teilbar ist durch v[j]. Ich denke, du meintest, es zu tun die andere Weise herum, d.h.:
```
if(v[j] % i == 0)
```
Recht nun, Sie drucken random Teiler von i ist. Sie werden nicht gedruckt, aus zufälligen zahlen, die sind bekannt, dass Sie nicht prim sein. Außerdem werden Sie Duplikate in Ihrer Ausgabe, vielleicht ist das ok.
- humm. ich denke, Sie wirklich wollen, wenn ((v[j] %i) == 0), um die richtigen Ergebnisse.
- hat eine höhere Priorität als ==.
InformationsquelleAutor Jeremy
4

First off, ich denke, Knuth sagte Sie zuerst: vorzeitige Optimierung ist die Ursache für viele Fehler. Machen Sie die langsame version, und dann herauszufinden, wie es schneller zu machen.

Zweite, für Ihre äußere Schleife, die Sie wirklich brauchen nur zu gehen, um sqrt(n) statt n.

InformationsquelleAutor mmr
2

Im Grunde, Sie haben eine Menge von unzusammenhängenden zahlen, so ist für jede eine, die Sie haben zu prüfen, ob es eine Primzahl.

Wenn Sie wissen, die Reihe der zahlen im Voraus, Sie können generieren, die alle Primzahlen, die kann auftreten, in diesem Bereich (oder die Wurzel davon), und testen Sie jede Zahl in Ihrem container für die Teilbarkeit durch eine der Primzahlen generiert.

Erzeugung der Primzahlen erfolgt am besten durch die Erathostenes Sieb - viele Beispiele gefunden werden, der Algorithmus.
- Wenn Sie die Menge der Primzahlen, die Sie gerade prüfen, ob die Zahl ist da, keine Notwendigkeit zu versuchen zu unterteilen, die von jedem.
InformationsquelleAutor xtofl
1

Sollten Sie versuchen, mit einem prime Sieb. Sie müssen wissen, die maximale Anzahl für die Erstellung des Siebes (O(n)) und Sie können dann bauen eine Menge der Primzahlen in diesem Bereich (O(max_element) oder wie die problem-Staaten O(1000) == O(1))), und überprüfen Sie, ob jede Zahl in der Menge der Primzahlen.

InformationsquelleAutor Motti
1

Dein code ist einfach nur falsch. Ersten, Sie Prüfung i % v[j] == 0, das ist vorwärts und rückwärts erklärt auch, warum man zahlen. Zweitens, das Ergebnis Duplikate enthalten, wie Sie die Prüfung und die Ausgabe jedes eingegebene Nummer jedes mal, wenn es fehlschlägt, wird der (defekte) Teilbarkeit testen.

Andere Vorschläge:

Mit n als der maximale Wert in den Vektor und die Anzahl der Elemente im Vektor ist verwirrend und sinnlos. Sie nicht brauchen, um pass in der Anzahl der Elemente im vector - Sie müssen nur die Abfrage der Vektor ist eine Größe. Und Sie können herausfinden, die max ziemlich schnell (aber wenn Sie es wissen vor der Zeit können Sie auch passieren in).

Wie oben erwähnt, müssen Sie nur testen, um sqrt(n) [wobei n den max-Wert in der vecotr]

Könnten Sie ein Sieb zu generieren, die alle Primzahlen bis n und dann entfernen Sie einfach diese Werte aus der input-Vektor, als auch oben vorgeschlagen. Dies kann schneller und einfacher zu verstehen, vor allem, wenn Sie speichern Sie die Primzahlen irgendwo.

Wenn du gehst, um zu testen, eine einzelne Zahl (mit, glaube ich, und inverse Sieb) dann schlage ich vor, testen jede Reihe einzeln, in der Reihenfolge. IMHO werden es einfacher zu verstehen als die Art und Weise haben Sie es geschrieben - testen Sie jede Zahl, die für die Teilbarkeit durch k < n für die immer k.

InformationsquelleAutor Rodyland
0

Die Idee mit dem Sieb, das Sie versuchen, zu implementieren, hängt von der Tatsache, dass Sie starten in einer prime - (2) und überqueren Scharen von, der Zahl - so dass alle zahlen, die abhängig von der prime "2" sind ausgeschlossen vorher.

Das ist, weil alle nicht Primzahlen sein können faktorisierten unten, um Primzahlen. In der Erwägung, dass Primzahlen sind nicht teilbar mit modulo 0, es sei denn, Sie teilen Sie Sie durch 1 oder durch sich selbst.

Also, wenn Sie wollen, verlassen Sie sich auf diesen Algorithmus, müssen Sie etwas bedeuten, um tatsächlich die Wiederherstellung dieser Eigenschaft des Algorithmus.

InformationsquelleAutor mstrobl

Dein code scheint haben viele Probleme:

Wenn Sie möchten, um zu testen, ob die Zahl eine Primzahl ist oder nicht-prime, würden Sie brauchen, um zu überprüfen, für v[j] % i == 0, nicht Umgekehrt
Sie nicht zu überprüfen, wenn Ihre Zahl geteilt durch sich selbst
Halten Sie auf überprüfen Sie Ihre zahlen wieder und wieder. Das ist sehr ineffizient.

Als die anderen Jungs vorgeschlagen hat, müssen Sie etwas tun, wie das Sieb des Eratosthenes.

So ein pseudo-C-code für dein problem wäre (habe ich noch nicht laufen diese durch Compiler noch, also bitte ignorieren syntax-Fehler. Dieser code beschreibt den Algorithmus nur)

vector<int> inputNumbers;

//First, find all the prime numbers from 1 to n
bool isPrime[n+1] = {true};
isPrime[0]= false;
isPrime[1]= false;
for (int i = 2; i <= sqrt(n); i++)
{
  if (!isPrime[i])
    continue;
  for (int j = 2; j <= n/i; j++)
    isPrime[i*j] = false;
}

//Check the input array for non-prime numbers
for (int i = 0; i < inputNumbers.size(); i++)
{
   int thisNumber = inputNumbers[i];
   //Vet the input to make sure we won't blow our isPrime array
   if ((0<= thisNumber) && (thisNumber <=n))
   {
      //Prints out non-prime numbers
      if (!isPrime[thisNumber])
         cout<< thisNumber;
   }
}

InformationsquelleAutor

0

Sortieren Sie zuerst die Rufnummer könnte ein guter Anfang sein - Sie können dies in nLogN Zeit. Das ist eine kleine Ergänzung (ich glaube) zu deinem anderen problem - der Feststellung, ob eine Zahl eine Primzahl ist.

(tatsächlich, mit einem kleinen Satz von zahlen, wie, dass Sie tun können, eine Art sich viel schneller mit einer Kopie der Größe der Vektor - /set und eine hash - /bucket-sort/was auch immer)

Ich würde dann die höchste Zahl in der Menge (ich nehme an, die zahlen können sich unbounded - nicht wissen, Obere Grenze, bis Ihr Art - oder haben Sie einen Durchgang zu finden, der max)

dann gehen Sie mit einem Sieb - wie schon andere gesagt haben

InformationsquelleAutor Tim

Jeremy ist Recht, das grundlegende problem ist, Ihre i % v[j] statt v[j] % i.

Versuchen Sie dies:

void sieve(vector<int> v, int n) {
  int i,j;

  for(j = 0; j <= n; j++) {
    cout << v[j] << ": ";

    for(i = 2; i < v[j]; i++) {
      if(v[j] % i == 0) {
        cout << "is divisible by " << i << endl;
        break;
      }
    }

    if (i == v[j]) {
      cout << "is prime." << endl;
    }
  }
}

Es ist nicht optimal, weil es versucht, eine Division durch alle zahlen kleiner als v[j] statt nur bis zur Quadratwurzel der v[j]. Und es wird versucht, Dividion & nbsp; durch alle zahlen statt nur Primzahlen.

Aber es funktioniert.

InformationsquelleAutor Jamie

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.