Trouver des nombres composés

Question

J'ai une gamme de nombres aléatoires. La plage est en fait déterminée par l'utilisateur, mais ce sera jusqu'à 1000 entiers. Ils sont placés dans ceci:

vector<int> n

et les valeurs sont insérées comme suit:

srand(1);

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

Je crée une fonction distincte pour rechercher toutes les valeurs non primordiales. Voici ce que j’ai maintenant, mais je sais que c’est complètement faux car j’ai la prime et la composite dans la 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;
           }
     }
}

Cette méthode fonctionnait généralement lorsque je ne disposais que d'une série de chiffres allant de 0 à 1 000, mais elle ne semble pas fonctionner maintenant, car les chiffres sont en désordre et en double. Existe-t-il une meilleure méthode pour trouver des nombres non premiers dans un vecteur? Je suis tenté de créer un autre vecteur, de le remplir avec n nombres et de trouver les non-premiers de cette façon, mais est-ce que ce serait inefficace?

D'accord, puisque la plage va de 0 à 1 000, je me demande s'il est plus facile de simplement créer un vecteur avec 0-n trié, puis d'utiliser un tamis pour trouver les nombres premiers, est-ce que cela se rapproche?

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

Dans ce code:

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

Vous testez votre index pour voir s'il est divisible par v [j]. Je pense que vous vouliez le faire à l'inverse, c'est-à-dire:

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

À l’heure actuelle, vous imprimez des diviseurs aléatoires de i. Vous n'imprimez pas des nombres aléatoires dont on sait qu'ils ne sont pas premiers. De plus, vous aurez des doublons dans votre sortie, peut-être que ça va.

Answer 2

Tout d'abord, je pense que Knuth l'a dit en premier: l'optimisation prématurée est la cause de nombreux bugs. Créez d'abord la version lente, puis déterminez comment la rendre plus rapide.

Deuxièmement, pour votre boucle externe, vous n'avez vraiment besoin que d'aller à sqrt (n) plutôt qu'à n.

Answer 3

En gros, vous avez beaucoup de nombres sans rapport, alors pour chacun, vous devrez vérifier s'il est premier.

Si vous connaissez la plage des nombres à l'avance, vous pouvez générer tous les nombres premiers que peut apparaître dans cette plage (ou son carré), et tester la divisibilité de chaque nombre de votre conteneur par l'un des nombres premiers générés.

Il est préférable de générer les nombres premiers avec le tamis d'Erathostenes - de nombreux exemples de cet algorithme sont disponibles.

Answer 4

Vous devriez essayer d'utiliser un premier crible . Vous devez connaître le nombre maximal pour créer le tamis (O(n)), puis vous pouvez créer un ensemble de nombres premiers dans cette plage (O(max_element) ou lorsque le problème indique O(1000) == O(1))) et vérifier si chaque nombre se trouve dans la liste. ensemble de nombres premiers.

Answer 5

Votre code est tout simplement faux. Tout d'abord, vous testez i% v [j] == 0, ce qui est une régression et explique également pourquoi vous obtenez tous les nombres. Deuxièmement, votre sortie contiendra des doublons au fur et à mesure que vous testez et sortez chaque nombre entré chaque fois que le test de divisibilité (rompu) échoue.

Autres suggestions:

Utiliser n comme valeur maximale dans le vecteur et le nombre d’éléments dans le vecteur est déroutant et inutile. Vous n'avez pas besoin d'indiquer le nombre d'éléments dans le vecteur - vous interrogez simplement la taille du vecteur. Et vous pouvez calculer le maximum assez rapidement (mais si vous le connaissez à l'avance, vous pouvez également le transmettre).

Comme mentionné ci-dessus, il vous suffit de tester sqrt (n) [où n est la valeur maximale dans le vecotr]

Vous pouvez utiliser un tamis pour générer tous les nombres premiers jusqu'à n, puis supprimer ces valeurs du vecteur d'entrée, comme suggéré également ci-dessus. Cela peut être plus rapide et plus facile à comprendre, surtout si vous stockez les nombres premiers quelque part.

Si vous voulez tester chaque nombre individuellement (à l'aide, je suppose, et au tamis inverse), je vous suggère de tester chaque nombre individuellement, dans l'ordre. IMHO, il sera plus facile à comprendre que la façon dont vous l'avez écrit - tester chaque nombre pour la divisibilité par k & Lt; n pour toujours augmenter k.

Answer 6

L'idée du tamis que vous essayez d'implémenter dépend du fait que vous commencez par un nombre premier (2) et que vous rayez des multitudes de ce nombre - donc tous les nombres qui dépendent du nombre premier! & "; 2 quot; sont exclus à l’avance.

En effet, tous les non-premiers peuvent être décomposés en nombres premiers. Considérant que les nombres premiers ne sont pas divisibles avec modulo 0 à moins que vous ne les divisiez par 1 ou par eux-mêmes.

Donc, si vous voulez utiliser cet algorithme, vous aurez besoin d'un moyen de restaurer réellement cette propriété de l'algorithme.

Answer 7

Votre code semble poser de nombreux problèmes:

1. Si vous voulez vérifier si votre nombre est premier ou non premier, vous devez vérifier v [j]% i == 0, et non l'inverse
2. Vous n'avez pas vérifié si votre numéro se divise tout seul
3. Vous continuez à vérifier vos numéros encore et encore. C'est très inefficace.

Comme d'autres personnes l'ont suggéré, vous devez faire quelque chose comme le tamis d'Eratosthène.

Donc, un pseudo-code C pour votre problème serait (je ne l'ai pas encore lu avec des compilateurs, donc ignorez les erreurs de syntaxe. Ce code est destiné à illustrer uniquement l'algorithme)

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

trier le numéro en premier pourrait être un bon début - vous pouvez le faire en temps nLogN. C’est un petit ajout (je pense) à votre autre problème - celui de savoir si un nombre est premier.
(En fait, avec un petit ensemble de chiffres comme celui-ci, vous pouvez faire un tri beaucoup plus rapidement avec une copie de la taille du vecteur / set et faire un tri avec hachage / seau / peu importe)

Je trouverais alors le nombre le plus élevé de la série (je suppose que les nombres peuvent être illimités - pas de limite supérieure connue jusqu'à ce que vous soyez triés - ou faire un seul passage pour trouver le maximum)

puis aller avec un tamis - comme d'autres l'ont dit

Answer 9

Jeremy a raison, le problème de base est votre i % v[j] au lieu de v[j] % i.

Essayez ceci:

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

Ce n'est pas optimal, car il tente de diviser par tous les nombres inférieurs à v[j] au lieu de se limiter à la racine carrée de <=>. Et il tente de diviser par tous les nombres au lieu de seuls les nombres premiers.

Mais cela fonctionnera.