Die Suche nach zusammengesetzten Zahlen

Question

Ich habe eine Reihe von Zufallszahlen. Der Bereich wird tatsächlich durch den Benutzer bestimmt, aber es wird bis zu 1000 ganzen Zahlen sein. Sie werden in dieser platziert:

vector<int> n

und die Werte werden wie folgt eingefügt:

srand(1);

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

Ich erstelle eine separate Funktion, die alle nicht-prime Werte zu finden. Hier ist was ich jetzt habe, aber ich weiß, es ist völlig falsch, wie ich beiden primen und Composite in der Serie zu bekommen.

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 funktioniert normalerweise auf, wenn ich nur eine Reihe von Zahlen von 0 bis 1000 hatte, aber es scheint nicht zu funktionieren jetzt, wenn ich Zahlen aus der Ordnung und Duplikate. Gibt es eine bessere Methode nicht-Primzahlen in einem Vektor zu finden? Ich bin versucht, nur einen anderen Vektor zu erstellen, füllen Sie es mit n Zahlen und finden nur die Nicht-Primzahlen so, aber das wäre ineffizient?

Okay, da der Bereich von 0 bis 1000 ist, ich frage mich, ob es einfacher ist, nur Vektor erstellen und mit 0-n sortiert und dann durch ein Sieb mit den Primzahlen zu finden, wird dies einen 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;
           }
     }
}

Answer 1

In diesem Code:

if(i % v[j] == 0)
  cout << v[j] << endl;

Sie testen Ihren Index, um zu sehen, wenn sie von v [j] teilbar sind. Ich denke, dass Sie es in die andere Richtung zu tun bedeutete um, das heißt:.

if(v[j] % i == 0)

Im Moment Sie drucken zufällige Teiler von i. Sie sind Ausdruck von nicht Zufallszahlen, die bekannt sind, nicht prim zu sein. Auch Sie werden Duplikate in Ihrer Ausgabe haben, vielleicht ist das in Ordnung.

Answer 2

Zunächst einmal denke ich, dass Knuth es die erste: vorzeitige Optimierung ist die Ursache vieler Fehler ist. Sprechen Sie die langsame Version zuerst, und dann herauszufinden, wie es schneller zu machen.

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

Answer 3

Im Grunde haben Sie eine Menge von nicht verwandten Zahlen, so dass für jeden müssen Sie prüfen, ob es Primes.

Wenn Sie den Bereich der Zahlen im Voraus kennen, können Sie alle Primzahlen erzeugen, dass können treten in diesem Bereich (oder die sqrt davon), und testen Sie jede Zahl in Ihrem Container für Teilbarkeit durch eine der erzeugten Primzahlen.

die Primzahlen generieren wird durch die Erathostenes Sieve erfolgt am besten -. Viele Beispiele dieses Algorithmus gefunden werden

Answer 4

Sie sollten versuchen, ein prime Sieb verwenden. Sie müssen die maximale Anzahl für die Erstellung des Siebes (O(n)) kennen und dann können Sie eine Reihe von Primzahlen in diesem Bereich (O(max_element) oder wie die Problemstaaten O(1000) == O(1))) bauen und prüfen, ob jede Zahl in der Menge der Primzahlen ist.

Answer 5

Der Code ist einfach falsch. Zuerst Sie testen i% v [j] == 0, die nach hinten und auch erklärt, warum Sie alle Zahlen zu bekommen. Zweitens wird die Ausgabe Duplikate enthält, wie Sie testen und jede Eingangsnummer jedes Mal, deren Ausgabe den (gebrochen) Teilbarkeit Test nicht besteht.

Andere Vorschläge:

Verwendung von n als den Maximalwert in dem Vektor und die Anzahl der Elemente in dem Vektor ist verwirrend und sinnlos. Sie müssen nicht in der Anzahl der Elemente in dem Vektor passieren - Sie abfragen, nur die Größe des Vektors. Und Sie können ziemlich schnell den max herauszufinden (aber wenn man es im Voraus wissen, können Sie auch geben es in).

Wie bereits erwähnt, müssen Sie nur testen (n) sqrt [wobei n der max-Wert im vecotr ist]

Sie könnten ein Sieb verwenden, um alle Primzahlen zu erzeugen bis zu n und entfernen Sie dann nur die Werte aus dem Eingangsvektor, wie auch oben vorgeschlagen. Dies kann schneller und einfacher sein, zu verstehen, vor allem wenn man die Primzahlen speichert irgendwo.

Wenn Sie vorhaben, jede Nummer einzeln testen (mit, ich denke, und inverses Sieb), dann schlage ich die Prüfung jede Nummer einzeln, in Ordnung. IMHO wird es leichter zu verstehen als die Art und Weise Sie es geschrieben haben -. Testen Sie jede Zahl für Teilbarkeit durch k

Answer 6

Die Idee des Siebes, die Sie versuchen, hängt von der Tatsache zu realisieren, dass Sie in bestem Start (2) und ausstreichen Schar von dieser Zahl - so ist alle Zahlen, die auf der prime „2“ abhängig sind von vornherein ausgeschlossen werden.

Das ist, weil alle nicht-Primzahlen faktorisiert bis zu Primzahlen werden kann. Während Primzahlen mit Modulo nicht teilbar sind 0, wenn Sie sie teilen, indem er 1 oder von ihnen selbst.

Also, wenn Sie auf diesen Algorithmus verlassen wollen, müssen Sie einige bedeuten eigentlich diese Eigenschaft des Algorithmus wiederherzustellen.

Answer 7

Der Code scheint viele Probleme zu haben:

1. Wenn Sie testen möchten, ob Ihre Zahl prim oder nicht prim ist, müssten Sie für v [j]% i == 0, nicht andersrum
prüfen
2. Sie haben nicht überprüfen, ob Ihre Nummer wird von selbst
Dividieren
3. Sie halten Ihre Zahlen immer wieder auf die Überprüfung. Das ist sehr ineffizient.

Wie andere Jungs vorgeschlagen, müssen Sie so etwas wie das Sieb des Eratosthenes tun.

So ein Pseudo-C-Code für Ihr Problem sein würde (ich habe das noch nicht durch Compiler laufen, so ignorieren Sie Syntaxfehler. Dieser Code ist der Algorithmus zur Veranschaulichung 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;
   }
}

Answer 8

Sortieren zuerst die Zahl einen guten Anfang sein könnte - Sie, dass in nlogn Zeit tun kann. Das ist ein kleiner Zusatz (glaube ich) zu Ihrem anderen Problem - das finden, wenn eine Zahl prim ist
. (Tatsächlich, mit einer kleinen Menge von Zahlen wie, dass man eine tun Art viel schneller mit einer Kopie der Größe des Vektors / Set und machen Ihnen einen Hash / Bucketsort / was auch immer)

Ich würde dann die höchste Zahl in der Menge finden (ich nehme die Zahlen unbegrenzt sein können - keine Obergrenze, bis die Art kennen - oder einen einzigen Durchlauf tun, um den max zu finden)

dann mit einem Sieb gehen - wie andere gesagt haben

Answer 9

Jeremy richtig ist, das Grundproblem ist Ihre i % v[j] statt v[j] % i.

Versuchen Sie folgendes:

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, da sie von allen Zahlen zu teilen sind versucht, weniger als v[j] statt nur bis zu der Quadratwurzel v[j]. Und es versucht dividion von allen Zahlen statt nur Primzahlen.

Aber es wird funktionieren.