Nombres premiers

Définition:

un nombre premier est un entier naturel qui admet exactement deux diviseurs entiers naturels.

Partie A test de primalité avec une boucle bornée

  1. On considère l'algorithme ci-dessous, traduire cet algorithme en une fonction Python $estprema(n)$ qui renvoie True si l'entier $n$ est premier et False sinon.

Fonction $estprema(n)$

Si $n<2$

renvoyer False

Si $n=2$

renvoyer True

Pour $i$ allant de $2$ à $n-1$

Si $i$ divise $n$

Renvoyer False

Renvoyer True


In [0]:
# Programme:
  1. Modifier la fonction afin qu'elle renvoie également une décomposition de l'entier $n$, par exemple $estprema(10)$ doit renvoyer $False,5,2$.

  2. Tester la fonction avec un nombre le nombre $50370952483$.

In [0]:
#Programme
(False, 502669, 100207)

Partie B test de primalité avec une boucle non bornée

On considère la fonction Python ci-dessous:

In [0]:
def estpremb(n):
  if n<2:
    return False
  if n==2:
    return True
  d=2
  while d*d<=n:
    if n%d==0:
      return False
    d=d+1
  return True
  1. Expliquer et justifier le choix de la condition à la ligne 7 du programme:

Répondre ici:

  1. Quel est le 1001 ème nombre premier?
In [0]:
# Programme

   

Répondre ici:

Partie C Fonction polynôme

En 1772, Léonard Euler étudie la fonction polynôme $P$ qui à un entier $n$ associe $P(n)=n^2+n+41$.

  1. Écrire une fonction Python qui prend un entier $n$ en paramètre et renvoie l'image de $n$ par $P$.
In [0]:
# Programme
  1. En utilisant la partie B, faire afficher le premier entier $n$ dont l'image par $P$ n'est pas un nombre premier.
  1. Modifier votre programme pour qu'il affiche la liste des nombres premiers obtenus avant d'atteindre un nombre composé.