La ricerca di numeri composti

Question

Ho una serie di numeri casuali.La gamma è in realtà determinata dall'utente, ma sarà fino a 1000 numeri interi.Essi sono posizionati in questo modo:

vector<int> n

e i valori vengono inseriti come questo:

srand(1);

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

Sto creando una funzione separata per trovare tutti i non primi valori.Qui è quello che ho ora, ma so che è completamente sbagliato in quanto mi sia primi e composti della 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;
           }
     }
}

Solitamente questo metodo ha funzionato quando ho appena avuto una serie di numeri da 0-1000, ma non sembra funzionare ora, quando ho i numeri di ordine e duplicati.C'è un metodo migliore per trovare i numeri non primi in un vettore?Ho la tentazione di creare un altro vettore, riempire con n numeri e basta trovare il non-primes in quel modo, ma sarebbe inefficiente?

Bene, dato che il range è da 0-1000 mi chiedo se è più facile creare il vettore con 0-n ordinati, e poi con un setaccio per trovare i numeri primi, è questo ottenere qualsiasi più vicino?

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 questo codice:

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

Si sta testando l'indice per vedere se è divisibile per v[j].Penso che dire di farlo in un altro modo, cioè:

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

Ora, la stampa casuale divisori dell'io.Non la stampa di numeri casuali che non sono noti per essere primo.Inoltre, si sono duplicati nella vostra uscita, forse è ok.

Answer 2

Prima di tutto, penso che Knuth detto prima:prematura di ottimizzazione è la causa di molti bug.Fare la versione lenta di prima, e poi di capire come renderlo più veloce.

In secondo luogo, per il ciclo esterno, è davvero solo bisogno di andare a sqrt(n) anziché n.

Answer 3

In sostanza, ci sono un sacco di estranei numeri, in modo che per ognuno si dovrà verificare se è primo.

Se si conosce la gamma dei numeri in anticipo, è possibile generare tutti i numeri primi che può si verificano nell'intervallo (o il sqrt esso), e test di ogni numero nel contenitore per la divisibilità per uno qualsiasi di generare numeri primi.

Generare i numeri primi è meglio farlo con il Erathostenes Sieve - molti esempi di tale algoritmo.

Answer 4

Si dovrebbe provare a utilizzare un primo setaccio.È necessario conoscere il numero massimo per la creazione di sieve (O(n)) e quindi è possibile costruire un insieme di numeri primi nell'intervallo (O(max_element) o come il problema stati O(1000) == O(1))) e controllare se ogni numero è nell'insieme dei numeri primi.

Answer 5

Il codice è semplicemente sbagliato.Primo, si stanno testando i % v[j] == 0, che è indietro e spiega anche perché è possibile ottenere tutti i numeri.Secondo, l'uscita contenere duplicati stai test e l'output di ogni numero di input ogni volta che non è l' (rotto) divisibilità di prova.

Altri suggerimenti:

Utilizzo di n il valore massimo del vettore e il numero di elementi del vettore è confuso e inutile.Non c'è bisogno di passare il numero di elementi del vettore, basta solo che la query del vettore di dimensione.E si può capire il max abbastanza velocemente (ma se si sa in anticipo che si può anche passare).

Come detto sopra, è solo bisogno di testare a sqrt(n) [dove n è il valore massimo in vecotr]

Si potrebbe utilizzare un setaccio per generare tutti i numeri primi fino a n e poi basta rimuovere tali valori, dall'ingresso del vettore, come anche suggerito sopra.Questo può essere più veloce e più facile da capire, soprattutto se si memorizzano i numeri primi da qualche parte.

Se si sta andando a testare ogni numero individualmente (utilizzando, credo, e l'inverso della sieve) allora vi suggerisco di testare ogni numero individualmente, in ordine.IMHO sarà più facile comprendere che il modo in cui hai scritto di test di ogni numero per la divisibilità per k < n per sempre crescenti di k.

Answer 6

L'idea del setaccio che si tenta di implementare dipende dal fatto che si avvia al primo (2) e una croce con una moltitudine di quel numero - tutti i numeri in modo che dipendono le prime "2" sono da escludere a priori.

Questo perché tutti i non-numeri primi possono essere factorized giù per i numeri primi.Considerando che i numeri primi non sono divisibili con modulo 0 a meno che non si divide per 1 o per se stessi.

Quindi, se si vuole utilizzare questo algoritmo, avrete bisogno di alcuni media effettivamente ripristinare questa proprietà dell'algoritmo.

Answer 7

Il codice sembra avere molti problemi:

1. Se si desidera verificare se il numero è primo o non primo, si avrebbe bisogno di controllare per v[j] % i == 0, e non viceversa
2. Non controllare se il tuo numero è la divisione di per sé
3. Voi continuate a controllare i numeri di nuovo e di nuovo.Che è molto inefficiente.

Come altri ragazzi suggerito, hai bisogno di fare qualcosa come il Crivello di Eratostene.

Così una pseudo codice C per il tuo problema potrebbe essere (non ho eseguito questo attraverso i compilatori di sicurezza, quindi, si prega di ignorare gli errori di sintassi.Questo codice è quello di illustrare l'algoritmo solo)

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

ordinamento prima il numero, potrebbe essere un buon inizio - si può fare in nLogN tempo.Che è una piccola aggiunta (credo) per il vostro altro problema di trovare se un numero è primo.
(in realtà, con una piccola serie di numeri che è possibile fare una specie molto più veloce con una copia della dimensione del vettore/set e fare un hash/bucket sort/altro)

Vorrei quindi trovare il numero più alto nella serie (presumo che i numeri possono essere illimitato - non conosce limite superiore fino a quando il tuo ordina: o fare una sola passata a trovare il max)

allora vai con un setaccio - come hanno detto gli altri

Answer 9

Jeremy è giusto, il problema di fondo è il tuo i % v[j] invece di v[j] % i.

Prova questo:

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;
    }
  }
}

Non è ottimale, perché è il tentativo di dividere per tutti i numeri minori di v[j] invece che solo fino a che la radice quadrata di v[j].Ed è il tentativo dividion di tutti i numeri, invece di solo i numeri primi.

Ma funzionerà.