Conseils utiles

Premier ou composé?

Pin
Send
Share
Send
Send


Comme vous le savez, les nombres naturels (sauf 1) sont divisés en nombres simples et composés, qui diffèrent par le nombre de diviseurs. Le nombre 1 ne peut pas être attribué à simple ou composite, car il n'a qu'un seul diviseur - 1. Le nombre premier n'en a que deux, en lequel il est divisible sans reste - il est aussi 1. Par exemple, le nombre 11 ne peut être décomposé qu'en 11 et 1, 17 en 17 et 1. Parmi des centaines de nombres de 1 à 100 il y a 25 nombres premiers. Il existe des nombres premiers et des quantités plus importantes, par exemple 331, 1979. Parallèlement, tout nombre composé peut être décomposé en plusieurs facteurs premiers. Par exemple, 6 peut être décomposé en 2 × 3, 144 peuvent être décomposés en 2 × 2 × 2 × 2 × 3 × 3. Un nombre naturel pouvant être décomposé en plus de deux facteurs est un composite. Chaque nombre composé étant supérieur à 1, il peut être représenté par le produit d'au moins deux entiers positifs supérieurs à 1. Tous les nombres pairs (à l'exception de 2) sont divisibles par 2, ce qui signifie qu'ils sont tous composites. L'exception concerne uniquement le nombre 2, qui est un nombre premier, car 1. En utilisant des nombres premiers, vous pouvez: réduire les fractions, déterminer le plus grand commun multiple, calculer le plus petit dénominateur commun, etc. Pour savoir si un nombre est premier, il existe des tables spéciales.

Pour déterminer plus rapidement si un nombre appartient à un nombre premier ou à un groupe de nombres composés, utilisez la calculatrice en ligne.

8 commentaires

Y a-t-il une différence à 100% entre eux?

La vérification de la divisibilité est le moyen de distinguer un nombre premier d'un composé. Un nombre premier est nécessairement impair (la seule exception est 2) et n'est pas divisible par 5. Par conséquent, si un nombre naturel se termine par 0, 2, 4, 5, 6 ou 8, il n'est certainement pas simple. Ensuite, vérifiez la divisibilité de 3, 7, 11, etc.

Les deux sont divisés en lui-même, comme n'importe quel nombre. Dans le même temps, deux est divisé par deux sous forme de nombre pair.

C’est donc une erreur de classer un deux en tant que nombre premier, ce qui est une absurdité logique.

Combien de diviseurs a un dieux? Deux: l'unité et vous-même. Par conséquent, correspond à la définition d'un nombre premier.

Si le nombre est pair, alors composez. Si étrange puis simple

Latifah, pas vraiment. Il y a un nombre premier pair - 2. Parmi les nombres impairs, il y a une infinité de constituants: 9, 15, 21, etc.

Le fait est que si vous divisez un point en vous-même, vous divisez un point en un point, car 2 = 2, donc, il a deux diviseurs: 1 et 2.

Oui, le nombre 2 a exactement deux diviseurs. Par conséquent, c'est un nombre premier.

Méthode 1 sur 4: Enumérer les diviseurs

L'énumération des diviseurs est le moyen le plus simple de déterminer la simplicité d'un nombre. Dans le cas de petits nombres, c'est peut-être le moyen le plus rapide. Il est basé sur la définition d'un nombre premier: un nombre est premier s'il n'a pas de diviseur autre que lui-même et l'unité.

  1. 1 Soit n un numéro de test. Selon cette méthode, vous devez diviser le nombre n en tous les diviseurs entiers possibles. Pour les grandes valeurs de n, par exemple n = 101, la vérification de chaque diviseur prendra beaucoup de temps. Mais il existe des moyens de réduire le nombre de diviseurs à vérifier.
  2. 2 Déterminez si le nombre n est pair. Tout nombre pair est divisible par 2. Si le nombre n est pair, nous pouvons immédiatement dire qu'il n'est pas premier (c'est-à-dire qu'il s'agit d'un nombre composé). Pour déterminer rapidement la parité d'un nombre, faites attention à son dernier chiffre. Si le dernier chiffre est 2, 4, 6, 8.0, le nombre est pair et non simple.
    • La seule exception à cette règle est le nombre 2. Comme il est complètement divisé uniquement par lui-même et par 1, le nombre 2 est un nombre premier. Ainsi, le nombre 2 est le seul nombre premier pair.
  3. 3 Divisez n par chaque nombre de 2 à n-1. Puisque le diviseur est inférieur au divisible, la vérification de tous les diviseurs inférieurs à n et supérieurs à 2 devrait indiquer si n est un nombre premier. Vous commencez avec un nombre supérieur à 2 car les nombres pairs (qui sont des multiples de 2) ne sont pas des nombres premiers. Ce n’est certainement pas le moyen le plus efficace de tester la simplicité des chiffres, mais il existe plusieurs méthodes pour optimiser la vérification.
    • Par exemple, vérifiez le nombre 11. Dans ce cas, divisez (complètement) 11 par 3, 4, 5, 6, 7, 8, 9, 10. Comme aucun de ces nombres ne divise (complètement) 11, le nombre 11 est premier. nombre.
  4. 4 Pour gagner du temps, vérifiez les diviseurs avec la valeur de la racine carrée arrondie (n). Vérifier tous les diviseurs de 2 à n-1 peut prendre beaucoup de temps. Par exemple, si vous souhaitez vérifier le nombre 103, vous devez alors tester les diviseurs suivants: 3, 4, 5, 6, 7. et ainsi de suite jusqu'à 102! Cela peut toutefois être évité - vérifiez uniquement les diviseurs compris entre 2 et la valeur de la racine carrée arrondie (n).
    • Explication de ce principe. Considérez les facteurs 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2, 100 × 1. Notez qu'après une paire de facteurs de 10 × 10 toutes les paires de facteurs sont répétées (seuls les facteurs de ces paires sont réorganisés). Par conséquent, vous pouvez ignorer les diviseurs de n plus grands que la racine carrée (n).
    • Par exemple, vérifiez n = 37. Il n’est pas nécessaire de tester tous les diviseurs de 3 à 36. Vérifiez plutôt les diviseurs compris entre 2 et la valeur de la racine carrée arrondie (37).
      • Racine carrée (37) = 6,08. Arrondis ce nombre à 7.
      • 37 n'est pas divisé par 3, 4, 5, 6, 7, donc c'est simple.
  5. 5 Pour gagner encore du temps, testez uniquement les diviseurs simples. Par définition, tout nombre composé peut être exprimé comme le produit de deux nombres premiers ou plus. Par conséquent, diviser le nombre n par un diviseur composite est une opération inutile qui répète la division multiple du nombre n en diviseurs principaux. Ainsi, vous pouvez affiner davantage la série de diviseurs testée.
    • Cela signifie que tous les diviseurs pairs et tous les diviseurs qui sont des multiples de nombres premiers peuvent être omis.
    • Par exemple, vérifiez le nombre 103. La racine carrée de 103 est arrondie à 11. Les diviseurs simples de 2 à 11 sont 3, 5, 7, 11. Les diviseurs 4, 6, 8, 9, 10 peuvent être omis (9 est un multiple de 3 et tous les autres diviseurs). Sont des nombres pairs). Ainsi, vous avez réduit le nombre de diviseurs testés à quatre.
      • Les diviseurs 3, 5, 7, 11 ne divisent pas (complètement) le nombre 103, il est donc premier.

Méthode 2: test à la ferme

En 1640, le mathématicien français Pierre Fermat a formulé pour la première fois un théorème (le petit théorème de Fermat), utilisé pour déterminer la simplicité d'un nombre. En fait, le test de Fermat sert à déterminer les nombres composés et non les nombres premiers. Ce test détermine avec certitude si le nombre est composite ou détermine si le nombre est «le plus probable». Le test de Fermat est utile dans les cas où l'énumération des diviseurs est peu pratique et lorsqu'une liste de nombres faisant exception au théorème est disponible.

  1. 1 Soit n un numéro de test. Comme indiqué ci-dessus, un test identifie parfois à tort les nombres composés comme des nombres premiers. Par conséquent, il est nécessaire de vérifier la réponse (la méthode de vérification de la réponse est décrite ci-dessous).
  2. 2 Sélectionnez un nombre entier «a» compris entre 2 et n-1.
    • Par exemple, vérifiez la simplicité du nombre 100. Supposons, a = 3.
  3. 3 calculer unn (mod n). Le calcul de cette expression nécessitera des connaissances en arithmétique modulaire. En arithmétique modulaire, lorsqu'une certaine valeur est appelée module, le comptage des nombres commence à zéro. Imaginez ceci comme une horloge: une heure l'après-midi correspond à 1 heure et non à 13 heures, c'est-à-dire que l'heure de l'après-midi est comptée à partir de zéro. Un module est désigné comme mod n. Alors calculez un n (mod n).
    • Une façon de calculer consiste à calculer un n, puis à diviser le résultat par n et à écrire le reste de la division en tant que réponse. Dans ce cas, il est recommandé d'utiliser des calculatrices spécialisées dotées d'une fonction de module, car elles calculent instantanément le reste lors de la division de grands nombres.
    • Dans notre exemple, en divisant 3 100/100, nous obtenons le reste 1. Ainsi, 3 100 (mod 100) = 1.
  4. 4 Si vous ne disposez pas d'une calculatrice spécialisée, utilisez la notation exponentielle du nombre lorsque vous calculez le reste manuellement.
    • Dans notre exemple, calculez manuellement 3 100 (mod 100). 3 100 = 515377520732011331036461129765621272702107522001 - un nombre énorme avec lequel il est difficile de travailler. Au lieu de travailler avec un numéro à 48 chiffres, imaginez 3 100 comme (((((((3 2 )*3) 2 ) 2 ) 2 )*3) 2 ) 2 . Rappelez-vous que lorsque vous augmentez une puissance à une puissance, les indicateurs sont multipliés: ((x y) z = x yz).
      • Déterminez maintenant le reste. Dans ((((((3 (2)) 3) 2) 2) 2) * 3) 2) 2, démarrez la solution avec des crochets internes et divisez le résultat par 100 à chaque fois. Utilisez le résultat dans les calculs suivants (et non comme réponse).
        • (((((((9) * 3) 2) 2) 2) * 3) 2) 2 - 9/100 - il n'y a pas de reste.
        • ((((((27 (2) 2) 2) 2) * 3) 2) 2 - 27/100 - il n'y a pas de reste.
        • ((((((729) 2) 2) * 3) 2) 2) 2 - 729/100 = 7 (arrêt 29). Restez 29. Continuez avec 29.
        • ((((29 2 =841) 2) * 3) 2) 2 - 841/100 = 8 (ost.41). Solde 41. Continuez avec 41.
        • (((41 2 = 1681) * 3) 2) 2 - 1681/100 = 16 (ost. 81). Solde 81. Continuez avec 81.
        • ((81*3 = 243) 2) 2 - 243/100 = 2 (arrêt 43). Solde 43. Continuer avec 43.
        • (43 2 = 1849) 2 - 1849/100 = 18 (ost. 49). Solde 49. Continuez avec 49.
        • 49 2 = 2401 - 2401/100 = 24 (arrêt 1). Le reste final est 1. Ainsi, 3 100 (mod 100) = 1 (le même résultat a été obtenu en calculant sur une calculatrice).
  5. 5 Vérifiez l’égalité:unn (mod n) = un (mod n) Si ce n'est pas observé, alors n est un nombre composé. S'il est observé, alors n est probablement un nombre premier (mais pas obligatoire). Répétez le test avec différentes valeurs «a» pour vous assurer que la réponse est correcte. Mais il existe des nombres composites qui satisfont la condition de Fermat pour toute valeur de a. On les appelle numéros de Carmichael (le plus petit d'entre eux est 561).
    • Dans notre exemple, 3 100 (mod 100) = 1 et 100 (mod 100) = 0. Ainsi, 1 ≠ 0 et 100 est un nombre composé.
  6. Utilisez les numéros Carmichael comme une garantie de la bonne réponse. Les nombres de Carmichael ont la forme (6k + 1) (12k + 1) (18k + 1) pour les valeurs entières de k lorsque chaque diviseur est premier. Vous pouvez trouver une liste complète des numéros Carmichael sur Internet.

Méthode 3 sur 3: Test de Miller-Rabin

Le test de Miller-Rabin détermine efficacement si un nombre est composite (et gère mieux les exceptions telles que les nombres de Carmichael).

  1. 1 Soit n un nombre impair qui doit être testé pour des raisons de simplicité.
  2. 2 Ecrivez n-1 sous la forme 2 s × d, où d est un nombre impair. Si n est premier, alors ça doit être étrange. Donc, n-1 est pair. Puisque n-1 est un nombre pair, il peut être représenté comme le produit de 2 dans une certaine mesure par un nombre impair. Par exemple, 4 = 2 2 × 1, 80 = 2 4 × 5, etc.
    • Par exemple, déterminez la simplicité d’un nombre n = 321. 321 - 1 = 320 et 320 = 2 6 × 5. C’est-à-dire que s = 6 et d = 5.
      • Par exemple, prenons le nombre plus complexe n = 371. 371 - 1 = 370 et 370 = 2 1 × 185. Soit d = 185, ce qui compliquera grandement les calculs.
  3. 3 Prenez n'importe quel nombre “a” compris entre 2 et n-1.
    • Dans notre exemple, pour n = 321, sélectionnez a = 100.
  4. 4 calculer und (mod n). Si und = 1 ou -1 (mod n), le nombre n passe le test de Miller-Rabin et est très probablement premier. Toutefois, ce test, à l'instar du test de Fermat, ne permet pas de déterminer la simplicité d'un nombre avec une certitude absolue.
    • Dans notre exemple, pour n = 321: a d (mod n) = 100 5 (mod 321). 100 5 = 10 000 000 000 (mod 321) = 313. Pour trouver le reste de 100 5/321, utilisez une calculatrice spécialisée ou un calcul manuel (décrit ci-dessus).
      • Puisque le résultat n'est pas 1 ou -1, vous ne pouvez pas dire que n est un nombre premier.
  5. 5 Si le résultat n'est pas 1 ou -1, calculez un 2d , un 4d , ... et ainsi de suite jusqu'à un 2 s-1 d . Si l'un des résultats est 1 ou -1 (mod n), le nombre n réussit le test de Miller-Rabin et est fort probablement simple. Si n réussit le test, vérifiez la réponse (voir étape suivante). Si n ne réussit aucun de ces tests, alors n est un nombre composé.
    • Rappelons que dans notre exemple, a = 100, s = 6, d = 5. Continuez à vérifier comme suit:
      • 100 2d = 10 = 1 × 10 20.
        • 1 × 10 20 (mod 321) = 64,64 1 ou -1. Continuez les calculs.
      • 100 4d = 20 = 1 × 10 40.
        • 1 × 10 40 (mod 321) = 244,24 1 ou -1.
      • Ici, vous pouvez terminer les calculs. s - 1 = 6 - 1 = 5. Vous avez atteint la valeur limite 4d = 2 2. Comme aucun des calculs n'a donné 1 ou -1, vous pouvez dire avec certitude que n = 321 est un nombre composé.
  6. 6 Si n réussit le test de Miller-Rabin, répétez le test avec différentes valeurs «a» pour vous assurer que la réponse est correcte. Si n est un nombre premier, il passera le test avec une valeur quelconque de «a». Si n est un nombre composé, au moins les trois quarts des valeurs de «a» échouent au test. Par conséquent, le test de Miller-Rabin est plus fiable que le test de Fermat, dans lequel les nombres de composés de Carmichael réussissent le test pour toute valeur de a.

Condition de tâche 2.30

Tâche 2.30
Étant donné un tableau unidimensionnel A, composé de nombres naturels. Affiche le nombre de nombres premiers dans le tableau.

Tout d’abord, laissez-moi vous rappeler ce que sont les primes.

Nombre premier - Ceci est un nombre naturel qui a exactement deux diviseurs naturels différents - l'unité et lui-même.

C'est-à-dire que si un nombre est divisible sans reste seulement par 1 et par lui-même, alors un tel nombre est premier.

Par exemple, les nombres premiers sont 2, 3, 5, etc.

Mais 4 n'est plus simple, puisqu'il est divisible non seulement par 1 et 4, mais aussi par 2.

Si vous avez oublié ce qu'est un nombre naturel, voyez ici.

Passons maintenant à la tâche. Nous avons essentiellement besoin d’un programme définissant les nombres premiers. Et trier les éléments d'un tableau dans une boucle et vérifier leurs valeurs est une question technique. Dans le même temps, nous pouvons non seulement compter, mais également afficher les nombres premiers du tableau.

Comment déterminer un nombre premier en Pascal

Je donnerai l'algorithme de la solution avec une analyse détaillée en Pascal. Vous pouvez voir la solution en C ++ dans l'exemple de programme en C ++.

IMPORTANT!
Beaucoup peuvent faire des erreurs à ce sujet. La définition dit qu'un premier a exactement deux différents diviseur. Par conséquent, le nombre 1 n'est pas premier (il n'est pas premier non plus, puisque zéro peut être divisé par n'importe quel nombre).

Nous vérifierons si le nombre est premier en utilisant une fonction que nous créerons nous-mêmes. Cette fonction retournera TRUE si le nombre est premier.

Dans la fonction, nous allons d'abord vérifier si le nombre est inférieur à deux. Si tel est le cas, il ne s'agit pas d'un nombre premier. Si le nombre est 2 ou 3, la procédure est simple et aucune vérification supplémentaire n'est requise.

Mais si le nombre N est supérieur à trois, dans ce cas, nous allons trier tous les diviseurs possibles, en partant de 2 à (N-1). Si le nombre N est divisible par un diviseur sans reste, alors ce n'est pas un nombre premier. Dans ce cas, nous cassons la boucle (car rien ne sert de vérifier davantage) et la fonction renvoie FALSE.

Cela n'a aucun sens de vérifier si le nombre est divisible par lui-même (le cycle ne dure donc que jusqu'à N-1).

Je ne fournirai pas la fonction elle-même ici - voyez-la dans les exemples de programmes.

Pin
Send
Share
Send
Send