Chargement de l'audio en cours
Plus

Plus

Tester si un nombre est premier
P.31

Mode édition
Ajouter

Ajouter

Terminer

Terminer

TP / TICE 2


Tester si un nombre est premier




Énoncé

Soit pp un nombre entier naturel.

Questions préliminaires :
1. Rappeler ce qu’est un nombre premier.

2. Donner un algorithme simple permettant de déterminer si un nombre pp est premier.
Voir les réponses

Objectif

Déterminer si pp est un nombre premier à l’aide d’une des deux méthodes.
MÉTHODE DE RÉSOLUTION 1
TABLEUR

1. Recopier la feuille de calcul ci-dessous.

Tester si un nombre est premier

2. À l’aide de l’instruction =MOD(a;b)\bf{=MOD(a\: ; b)} qui donne le reste de la division euclidienne d’un nombre entier aa par un nombre entier bb, écrire dans D2 une formule qui affiche le reste de la division de A2 par C2. Puis tirer cette formule vers le bas, jusqu’à la cellule D19.

3. À l’aide de la fonction =PRODUIT()\bf{= PRODUIT()} et de la fonction =SI()\bf{= SI()}, écrire une formule dans A4 qui affiche « premier » si le nombre situé en A2 est premier.

4. À l’aide de cette méthode, tester la primalité de 77 ; 2929 et 91.91.


5. Pour n400n \geqslant 400 , le tableur semble ne plus pouvoir fonctionner correctement. Pour tester la primalité d’un entier inférieur à 1000010\,000, pourquoi est-il suffisant de tester les nombres uniquement jusqu’à 100100 ? (Voir Pour aller plus loin ci-après.)
Voir les réponses
MÉTHODE DE RÉSOLUTION 2
PYTHON

1. On complétera le programme ci-dessous au fur et à mesure des questions.

def Premier(nombre) :
	ntest = ...
  reponse = True
  while ... :
  	if ... :
      reponse = False
    ntest = ntest + 1
  return(...)
Voir les réponses

2. À l’aide de l’instruction a%b\bf{a \% b} qui donne le reste de la division d’un nombre entier aa par un nombre entier bb , compléter le test de la ligne 5.

3. Quelle valeur doit on affecter à la variable ntest\bf{ntest} à la ligne 2 ?


4. Compléter la ligne 4 du programme.

5. Tester la primalité de 77 ; 2929 ; 9191 et 529529 à l’aide de cette méthode.
Voir les réponses

Pour aller plus loin


L’algorithme utilisé ici pour tester si un nombre est premier est très gourmand en calcul. Avec des outils tels qu’un tableur, cela peut vite poser problème.

1. Combien d’opérations sont nécessaires pour tester si 1111 est premier ? Et pour 997997 ?


2. Pour savoir si un entier naturel non nul pp est premier, il suffit en fait de tester tous les entiers jusqu’à p.\sqrt{p} .
a. Avec cette méthode, combien d’opérations sont nécessaires pour déterminer si 997997 est premier ?

b. Pourquoi cette méthode fonctionne-t-elle ?


Le crible d’Ératosthène permet de déterminer tous les nombres premiers avec un algorithme particulier. Pourtant, cet algorithme n’est pas utilisé pour les grands nombres. Trouver comment fonctionne le crible d’Ératosthène et déterminer ses limites d’utilisation.

Voir les réponses
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service.
Pour plus d’informations, cliquez ici.