1. Compléter la fonction premier qui prend en argument un nombre entier strictement positif et qui retourne True si ce nombre est premier et False sinon.

2. Expliquer la ligne 7 de cette fonction.

3. Justifier pourquoi cette ligne peut être remplacée par for i in range(2, int(sqrt(n)) + 1).

4. À l'aide de l'instruction clock du module time, qui permet de chronométrer un programme, évaluer le gain de temps obtenu avec cette modification sur différents nombres premiers. On pourra par exemple introduire les lignes suivantes.

Le zoom est accessible dans la version Premium.

def premier(n):
  if n == 1:
    return False
  if n == 2:
    return True
  else:
    for i in range(2, n):
      if ... :
        return False
  return True

2
Fréquence des carrés modulo 7

→

Voir fiche n° 2 : Les variables

https://assets.lls.fr/pages/13454769/fiche-n2-les-variables.pdf

→

Voir fiche n° 2 bis : Les listes

https://assets.lls.fr/pages/13595880/fichen2bisleslistes.pdf

→

Voir fiche n° 5 : Les boucles bornées

http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE5_LES_BOUCLES_BORNEES.pdf

1. À l'aide d'une feuille de calcul, déterminer le reste dans la division euclidienne par

7

de chacun des carrés des nombres entiers compris entre

0

100

. Certains restes semblent-ils apparaître plus souvent que d'autres ?

2. Le programme suivant calcule la fréquence de chaque congruence modulo 7 parmi les carrés des nombres entiers strictement positifs. Compléter les lignes 4 et 8 de ce programme.

3. Après avoir lancé ce programme, pouvez vous confirmer le résultat de la question 1 ?

N = 1000
congruence = [0, 0, 0, 0, 0, 0, 0]
for i in range(N):
  reste = ...
  congruence[reste] = congruence[reste] + 1

# calcul des fréquences
for k in range(len(congruence)):
  congruence[k] = ...

print(congruence)

3
Calcul du $PGCD$ par l'algorithme d'Euclide

→

Voir fiche n° 2 : Les variables

https://assets.lls.fr/pages/13454769/fiche-n2-les-variables.pdf

→

Voir fiche n° 3 : Les fonctions

http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE3_LES_FONCTIONS.pdf

→

Voir fiche n° 6 : Les boucles non bornées

http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE6_LES_BOUCLES_NON_BORNEES.pdf

Les fonctions euclide_iteratif et euclide_recursif permettent de calculer le

PGCD

de deux nombres entiers naturels

a

b

donnés en arguments.

1. Compléter la fonction euclide_iteratif.

2. Compléter la fonction euclide_recursif.

def euclide_iteratif(a, b):
  a, b = max(a, b), min(a, b)
  reste = b
  while a%b … :
    reste = a%b
    a, b = ... , ...
  return ...
  
def euclide_recursif(a, b):
  a, b = max(a, b), min(a, b)
  if a%b == 0:
    return ...
  else:
    return ...

4
Calcul du $PGCD$ par balayage

→

Voir fiche n° 2 : Les variables

https://assets.lls.fr/pages/13454769/fiche-n2-les-variables.pdf

→

Voir fiche n° 3 : Les fonctions

http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE3_LES_FONCTIONS.pdf

→

Voir fiche n° 4 : Les instructions conditionnelles

http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE4_LES_INSTRUCTIONS_CONDITIONNELLES.pdf

→

Voir fiche n° 5 : Les boucles bornées

http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE5_LES_BOUCLES_BORNEES.pdf

La fonction pgcd_balayage renvoie le

PGCD

de deux nombres entiers

a

b

donnés en arguments. Pour ce faire, la fonction teste tous les nombres inférieurs à

a

b

et conserve, parmi ceux qui divisent

a

b

, le plus grand. Compléter la fonction.

def pgcd_balayage(a, b):
  for i in range(...):
    if a%i == 0 and ... :
      pgcd = ...
  return pgcd

5
Conjectures

n \in N

7 n + 4

5 n + 3

étaient premiers entre eux.

1. À l'aide de la fonction euclide_recursif de l'exercice 3 (à compléter), écrire une fonction permettant de tester cette affirmation pour tous les nombres entiers inférieurs à une valeur

N \in N

donnée en argument.

2. Démontrer cette conjecture.

3. Par ailleurs, Jérôme a lu que, pour tout entier naturel non nul

n

\frac{2 n + 1}{n ( n + 1 )}

est irréductible. En modifiant la fonction de la question 1, estimer la validité de cette conjecture.

4. Prouver cette conjecture.

def euclide_recursif(a, b):
  a, b = max(a, b), min(a, b)
  if a%b == 0:
    return ...
  else:
    return ...

6
Nombre de diviseurs

→
Voir fiche n° 1 : Algorithme en langage naturel
http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE1_ALGORITHME_EN_LANGAGE_NATUREL.pdf

→
Voir fiche n° 2 : Les variables
https://assets.lls.fr/pages/13454769/fiche-n2-les-variables.pdf

→
Voir fiche n° 3 : Les fonctions
http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE3_LES_FONCTIONS.pdf

→
Voir fiche n° 4 : Les instructions conditionnelles
http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE4_LES_INSTRUCTIONS_CONDITIONNELLES.pdf

→
Voir fiche n° 5 : Les boucles bornées
http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE5_LES_BOUCLES_BORNEES.pdf

1. Écrire une fonction nombre_diviseurs qui prend en argument un nombre entier non nul

n

et qui retourne le nombre de ses diviseurs.

2. Écrire une fonction max_diviseurs qui prend en argument un nombre entier

n

non nul et qui retourne le nombre entier

k ⩽ n

ayant le plus grand nombre de diviseurs. Si deux nombres ou plus ont le même nombre de diviseurs, la fonction renverra le plus petit de ces nombres.

3. Modifier le programme pour qu'en cas d'égalité sur le nombre de diviseurs, la fonction retourne le plus grand des nombres concernés.

7
Théorème de Wilson

p

strictement plus grand que

1

est un nombre premier si, et seulement si, il divise

(p - 1)! + 1

, c'est-à-dire si, et seulement si,

(p - 1)! + 1 \equiv 0 [p]

.

1. En utilisant éventuellement la fonction factorial du module math, écrire à l'aide du théorème de Wilson, une fonction estPremier qui prend en argument un entier naturel

n

supérieur ou égal à

2

et renvoie True si l'entier est premier et False sinon.

2. Vérifier pour les entiers inférieurs ou égaux à

10000

que le test de primalité présenté dans l'

exercice 1

et celui du théorème de Wilson donnent les mêmes résultats.

3. Expliquer pourquoi ce test, malgré sa simplicité apparente, n'est pas utilisé dans les tests de primalité informatiques.

8
Nombres pseudo-aléatoires

→
Voir fiche n° 2 : Les variables
https://assets.lls.fr/pages/13454769/fiche-n2-les-variables.pdf

→
Voir fiche n° 3 : Les fonctions
http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE3_LES_FONCTIONS.pdf

→
Voir fiche n° 4 : Les instructions conditionnelles
http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE4_LES_INSTRUCTIONS_CONDITIONNELLES.pdf

Pour générer une suite de nombres pseudo‑aléatoires, c'est-à-dire une suite de nombres présentant certaines propriétés du hasard, on peut utiliser des suites d'entiers définies, pour tout entier naturel

n

, par

u_{n + 1} = a u_{n} + c [m]

, où

a

c

m

sont trois nombres entiers appelés respectivement le multiplicateur, l'incrément et le module. Le premier terme

u_{0}

, nombre entier compris entre

0

m - 1

, est appelé graine.

1. Dans cette question, on choisit

a = 25

c = 16

m = 256

. En utilisant des graines égales à

125

96

50

10

, expliquer pourquoi les suites générées ne conviennent pas comme suites de nombres pseudo‑aléatoires.

2. Expliquer pourquoi une suite générée par cette méthode est nécessairement périodique. Préciser quelle valeur la période ne peut pas dépasser.

3. Écrire une fonction Python nommée periode qui prend en arguments

a

c

m

u_{0}

et retourne la période de la suite.

def u(n, a, c, m, u_0):
  if (n == 0):
    return u_0
  else:
    return (a*u(n-1, a, c, m, u_0) + c)%m

9
Décomposition en produit de facteurs premiers

→
Voir fiche n° 2 : Les variables
https://assets.lls.fr/pages/13454769/fiche-n2-les-variables.pdf

→
Voir fiche n° 3 : Les fonctions
http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE3_LES_FONCTIONS.pdf

→
Voir fiche n° 5 : Les boucles bornées
http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE5_LES_BOUCLES_BORNEES.pdf

La fonction decomposition_vers_nombre ci-dessous permet de calculer un nombre à partir de sa décomposition en produit de facteurs premiers.

1. En étudiant la fonction, sous quelle forme doit être écrite la décomposition en produit de facteurs premiers d'un nombre pour que le script fonctionne correctement ?

2. Tester cette fonction avec M=[[2,1],[3,2],[5,3]].

3. Écrire une fonction qui prend en argument un nombre entier naturel inférieur ou égal à

1000

et qui renvoie sa décomposition en produit de facteurs premiers.

La liste des nombres premiers inférieurs ou égaux à

1000

est fournie ci-dessous.

Aide

def decomposition_vers_nombre(M):
  nombre = 1
  n = len(M)
  for facteur in range(n):
    nombre = nombre * M[facteur][0]**M[facteur][1]
  return nombre
 
liste_nombres_premiers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

10
Divisibilité par 24

→
Voir fiche n° 2 : Les variables
https://assets.lls.fr/pages/13454769/fiche-n2-les-variables.pdf

→
Voir fiche n° 3 : Les fonctions
http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE3_LES_FONCTIONS.pdf

→
Voir fiche n° 4 : Les instructions conditionnelles
http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE4_LES_INSTRUCTIONS_CONDITIONNELLES.pdf

→
Voir fiche n° 5 : Les boucles bornées
http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE5_LES_BOUCLES_BORNEES.pdf

1. Démontrer que si

p

est un nombre premier supérieur ou égal à

5

, alors

p^{2} - 1

est un multiple de

24

2. On choisit un nombre entier naturel

n

inférieur ou égal à

1000

tel que

n^{2} - 1

soit divisible par

24

. Estimer à l'aide d'une fonction Python la probabilité que

n

soit un nombre premier.

On pourra utiliser le test de primalité construit dans un exercice précédent.

Aide

11
$PPCM$

→

Voir fiche n° 2 : Les variables

https://assets.lls.fr/pages/13454769/fiche-n2-les-variables.pdf

→

Voir fiche n° 3 : Les fonctions

http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE3_LES_FONCTIONS.pdf

→

Voir fiche n° 4 : Les instructions conditionnelles

http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE4_LES_INSTRUCTIONS_CONDITIONNELLES.pdf

→

Voir fiche n° 5 : Les boucles bornées

http://lls-ftp.s3.amazonaws.com/collection-2019/python/FICHE5_LES_BOUCLES_BORNEES.pdf

Le code ci-dessous permet de déterminer le

PGCD

de deux nombres dont on donne la décomposition en produit de facteurs premiers. Utiliser ce code pour écrire une fonction Python permettant de calculer le

PPCM

de deux nombres donnés.

list.index(x) retourne la position du premier élément de la liste list ayant la valeur x.

Aide

def pgcd(nb1, nb2):
  n1 = len(nb1)
  n2 = len(nb2)
  
  out = []
 
  liste1 = []
  for i in range(n1):
    liste1.append(nb1[i][0])
  
  liste2 = []
  for j in range(n2):
    liste2.append(nb2[j][0])
  
  for facteur in range(n1):
    if liste1[facteur] in liste2:
      index = liste2.index(liste1[facteur])
      exposant = min(nb1[facteur][1], nb2[index][1])
      out.append([liste1[facteur], exposant])
  
  return out
 
a = [[2,5],[5,3],[7,1]]
b = [[2,3],[3,2],[5,4]]