TP / TICE 2


Tester si un nombre est premier




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.


Objectif

Déterminer si pp est un nombre premier à l’aide d’une des deux méthodes.

É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.
MÉTHODE DE RÉSOLUTION 1
TABLEUR

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

1. Recopier la feuille de calcul ci-dessous.

Tester si un nombre est premier
MÉTHODE DE RÉSOLUTION 2
PYTHON

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.

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(...)
Connectez-vous pour ajouter des favoris

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

Se connecter

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.

Dites-nous qui vous êtes !

Pour assurer la meilleure qualité de service, nous avons besoin de vous connaître !
Cliquez sur l'un des choix ci-dessus qui vous correspond le mieux.

Nous envoyer un message




Nous contacter?