Chargement de l'audio en cours
Cacher

Cacher

Plus

Plus


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.

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.)
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(...)

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.

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.

Connectez-vous pour ajouter des favoris

Pour pouvoir ajouter ou retrouver des favoris, nous devons les lier à votre compte.Et c’est gratuit !

Livre du professeur

Pour pouvoir consulter le livre du professeur, vous devez être connecté avec un compte professeur et avoir validé votre adresse email académique.

Votre avis nous intéresse !
Recommanderiez-vous notre site web à un(e) collègue ?

Peu probable
Très probable

Cliquez sur le score que vous voulez donner.