Encontrando números compósitos

Question

Eu tenho um intervalo de números aleatórios. A gama é realmente determinado pelo usuário, mas será até 1000 números inteiros. Eles são colocados no seguinte:

vector<int> n

e os valores são inseridos como esta:

srand(1);

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

Estou criando uma função separada para encontrar todos os valores não-prime. Aqui está o que eu tenho agora, mas eu sei que é completamente errado como eu ficar tanto prime e composta na série.

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 normalmente funcionou quando eu só tinha uma série de números 0-1000, mas não parece estar funcionando agora quando eu tenho os números fora de ordem e duplicatas. Existe um método melhor para encontrar números não primos em um vetor? Estou tentado a apenas criar outro vetor, preenchê-lo com n números e apenas encontrar os não-primes dessa maneira, mas isso seria ineficiente?

Tudo bem, desde que o intervalo é de 0-1000 Eu estou querendo saber se é mais fácil simplesmente criar vector com 0-n classificadas, e em seguida, usando uma peneira para encontrar os números primos, é esta ficando mais perto?

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

Neste código:

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

Você está testando o seu índice para ver se ele é divisível por v [j]. Eu acho que você quis fazer o contrário, ou seja:.

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

Agora, você está imprimindo divisores aleatórios de i. Você não está imprimindo números aleatórios que são conhecidos para não ser nobre. Além disso, você terá duplicatas em sua saída, talvez, que é ok.

Answer 2

Primeiro, eu acho que Knuth disse primeiro: otimização prematura é a causa de muitos erros. Faça a versão lenta primeiro, e depois descobrir como torná-lo mais rápido.

Em segundo lugar, para o seu loop externo, você realmente só precisa ir para sqrt (n) em vez de n.

Answer 3

Basicamente, você tem um monte de números não relacionados, por isso para cada um que você terá que verificar se é nobre.

Se você sabe que a gama dos números com antecedência, você pode gerar todos os números primos que pode ocorrer nesse intervalo (ou o sqrt dela), e testar todos os números em seu recipiente para divisibilidade por qualquer um dos primos gerados.

Gerar os números primos é o melhor feito pela Eratóstenes Sieve -. Muitos exemplos a ser encontrados desse algoritmo

Answer 4

Você deve tentar usar um nobre peneira . Você precisa saber o número máximo para a criação da peneira (O(n)) e, em seguida, você pode construir um conjunto de números primos nesse intervalo (O(max_element) ou como o problema afirma O(1000) == O(1))) e verifique se cada número está no conjunto dos números primos.

Answer 5

Seu código é apenas errado liso. Primeiro, você está testando% v i [j] == 0, que é para trás e também explica por que você começa todos os números. Em segundo lugar, a sua saída conterá duplicatas como você está testando e produzir cada número de entrada cada vez que não o (quebrado) teste de divisibilidade.

Outras sugestões:

Usando n como o valor máximo no vector e o número de elementos no vector é confuso e inútil. Você não precisa passar no número de elementos no vector - basta consultar o tamanho do vetor. E você pode descobrir o máximo rapidamente (mas se você sabe que antes do tempo assim como você pode passá-lo).

Como mencionado acima, você só precisa de teste para sqrt (n) [onde n é o valor máximo na vecotr]

Você pode usar uma peneira para gerar todos os números primos até N e em seguida, basta remover os valores do vetor de entrada, como também sugerido acima. Isso pode ser mais rápido e mais fácil de entender, especialmente se você armazenar os números primos em algum lugar.

Se você estiver indo para testar cada número individualmente (usando, eu acho, e peneira inversa), então eu sugiro testar cada número individualmente, em ordem. IMHO vai ser mais fácil de entender do que a maneira que você escreveu ele -. Testando cada número de divisibilidade por k

Answer 6

A idéia da peneira que você tentar implementar depende do fato de que você começa em um prime (2) e atravessar a multidão de esse número - então todos os números que dependem do prime "2" são descartadas de antemão.

Isso porque todos os não-primes pode ser fatorado até primos. Considerando primos não são divisíveis com modulo 0 a menos que você dividi-los por 1 ou por elas próprias.

Então, se você quer contar com esse algoritmo, você vai precisar de algum meio para realmente restaurar esta propriedade do algoritmo.

Answer 7

Seu código parece ter muitos problemas:

1. Se você quiser testar se o seu número é primo ou não-prime, você precisa verificar se há v [j]% i == 0, não o contrário
2. Você não verificar se o seu número está a dividir por si só
3. Você continua a verificar seus números de uma e outra vez. Isso é muito ineficiente.

Como outros caras sugeriu, você precisa fazer algo parecido com o Crivo de Eratóstenes.

Assim, um pseudo-código C para o seu problema seria (eu não executar isto através de compiladores ainda, então por favor ignore erros de sintaxe. Este código é para ilustrar o algoritmo apenas)

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

classificando o primeiro número pode ser um bom começo - você pode fazer isso em tempo nlogn. Esse é um pequeno acréscimo (eu acho) para o seu outro problema -. O de encontrar se um número é primo
(Na verdade, com um pequeno conjunto de números como esse você pode fazer uma espécie muito mais rápido com uma cópia do tamanho do vetor / set e fazer um hash / bucket sort / whatever)

Eu, então, encontrar o número mais alto no conjunto (eu assumo os números podem ser ilimitada - não sei limite superior até que seu tipo - ou fazer uma única passagem para encontrar o max)

, em seguida, ir com uma peneira - como já foi dito

Answer 9

Jeremy é certo, o problema básico é o seu i % v[j] vez de v[j] % i.

Tente isto:

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

Não é ideal, porque ele está tentando dividir por todos os números menos de v[j] em vez de apenas até a raiz quadrada de v[j]. E ele está tentando dividion por todos os números em vez de apenas números primos.

Mas ele vai trabalhar.