Encontrar números compuestos

Question

Tengo un rango de números aleatorios. El rango lo determina realmente el usuario, pero será de hasta 1000 enteros. Se colocan en esto:

vector<int> n

y los valores se insertan así:

srand(1);

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

Estoy creando una función separada para encontrar todos los valores no primos. Esto es lo que tengo ahora, pero sé que está completamente mal, ya que obtengo tanto prime como composite en la 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;
           }
     }
}

Este método generalmente funcionaba cuando tenía una serie de números del 0 al 1000, pero no parece funcionar ahora cuando tengo números fuera de servicio y duplicados. ¿Existe un mejor método para encontrar números no primos en un vector? Estoy tentado de crear otro vector, llenarlo con n números y simplemente encontrar los no primos de esa manera, pero ¿sería ineficiente?

Bien, dado que el rango es de 0-1000, me pregunto si es más fácil crear un vector con 0-n ordenado, y luego usar un tamiz para encontrar los números primos, ¿se está acercando esto?

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

En este código:

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

Está probando su índice para ver si es divisible por v [j]. Creo que querías hacerlo al revés, es decir:

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

En este momento, está imprimiendo divisores aleatorios de i. No está imprimiendo números aleatorios que se sabe que no son primos. Además, tendrá duplicados en su salida, tal vez eso esté bien.

Answer 2

Primero, creo que Knuth lo dijo primero: la optimización prematura es la causa de muchos errores. Primero haga la versión lenta y luego descubra cómo hacerlo más rápido.

Segundo, para su ciclo externo, realmente solo necesita ir a sqrt (n) en lugar de n.

Answer 3

Básicamente, tiene muchos números no relacionados, por lo que para cada uno tendrá que verificar si es primo.

Si conoce de antemano el rango de los números, puede generar todos los números primos que pueden aparecer en ese rango (o el sqrt del mismo), y probar la divisibilidad por cada número en su contenedor cualquiera de los primos generados.

La generación de los primos se realiza mejor con el Erathostenes Sieve; se pueden encontrar muchos ejemplos de ese algoritmo.

Answer 4

Debería intentar usar un primer tamiz . Debe conocer el número máximo para crear el tamiz (O(n)) y luego puede construir un conjunto de números primos en ese rango (O(max_element) o como indica el problema O(1000) == O(1))) y verificar si cada número está en el conjunto de primos.

Answer 5

Su código es simplemente incorrecto. Primero, está probando i% v [j] == 0, que está al revés y también explica por qué obtiene todos los números. En segundo lugar, su salida contendrá duplicados mientras está probando y enviando cada número de entrada cada vez que falle la prueba de divisibilidad (rota).

Otras sugerencias:

Usar n como el valor máximo en el vector y el número de elementos en el vector es confuso e inútil. No es necesario que pase el número de elementos en el vector, solo debe consultar el tamaño del vector. Y puede calcular el máximo con bastante rapidez (pero si lo sabe con anticipación, también puede pasarlo).

Como se mencionó anteriormente, solo necesita probar sqrt (n) [donde n es el valor máximo en el vecotr]

Podría usar un tamiz para generar todos los primos hasta ny luego simplemente eliminar esos valores del vector de entrada, como también se sugirió anteriormente. Esto puede ser más rápido y más fácil de entender, especialmente si almacena los números primos en algún lugar.

Si vas a probar cada número individualmente (usando, supongo, y tamiz inverso), entonces sugiero probar cada número individualmente, en orden. En mi humilde opinión, será más fácil de entender que la forma en que lo has escrito: probando la divisibilidad de cada número por k & Lt; n por cada vez mayor k.

Answer 6

La idea del tamiz que intentas implementar depende del hecho de que comienzas con un primo (2) y tachas multitudes de ese número, de modo que todos los números que dependen del primo " 2 quot; se descartan de antemano.

Esto se debe a que todos los no primos pueden factorizarse en primos. Mientras que los primos no son divisibles con el módulo 0 a menos que los divida por 1 o por sí mismos.

Entonces, si desea confiar en este algoritmo, necesitará algún medio para restaurar realmente esta propiedad del algoritmo.

Answer 7

Su código parece tener muchos problemas:

1. Si desea probar si su número es primo o no primo, necesitaría verificar v [j]% i == 0, no al revés
2. No comprobaste si tu número se está dividiendo por sí mismo
3. Sigues revisando tus números una y otra vez. Eso es muy ineficiente.

Como sugirieron otros muchachos, debes hacer algo como el Tamiz de Eratóstenes.

Entonces, un pseudo código C para su problema sería (todavía no lo he ejecutado a través de compiladores, así que ignore los errores de sintaxis. Este código es solo para ilustrar el algoritmo)

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

ordenar el número primero puede ser un buen comienzo; puede hacerlo en tiempo nLogN. Esa es una pequeña adición (creo) a su otro problema: el de encontrar si un número es primo.
(en realidad, con un pequeño conjunto de números como ese, puede hacer una clasificación mucho más rápido con una copia del tamaño del vector / conjunto y hacer un hash / clasificación de cubo / lo que sea)

Luego encontraría el número más alto en el conjunto (supongo que los números pueden ser ilimitados, sin conocer el límite superior hasta su clasificación, o hacer una sola pasada para encontrar el máximo)

luego vaya con un tamiz, como han dicho otros

Answer 9

Jeremy tiene razón, el problema básico es tu i % v[j] en lugar de v[j] % i.

Prueba esto:

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

No es óptimo, porque intenta dividir entre todos los números menores que v[j] en lugar de solo hasta la raíz cuadrada de <=>. Y está intentando la división por todos los números en lugar de solo primos.

Pero funcionará.