2- Listes

En informatique, on est souvent amené à représenter des listes de valeurs. Par exemple, la liste des élèves d'une classe.

Le type list de Python sert justement à représenter de tels objets.

Python

Loading editor...

fruits = ["Pomme", "Poire", "Fraise", "Tomate", "Abricot"]
print(fruits)

Indexation et slicing

Pour récupérer l'élément n° i d'une liste :

Python

Loading editor...

print(fruits[0]) # affiche le premier élément
print(fruits[1]) # affiche le deuxième élément
print(fruits[-1]) # affiche le dernier élément

Le print sert ici à afficher le résultat pour l'exemple : il n'est pas nécessaire pour récupérer un élément d'une liste.

Les indices commencent à 0. Si on a une liste de longueur 5, le dernier élément est donc à l'indice 4.

On peut également utiliser des indices négatifs : l'indice -1 correspond au dernier élément, -2 à l'avant-dernier, etc.

On peut aussi directement récupérer une sous-liste, avec ce qu'on appelle le slicing.

Python

Loading editor...

print(fruits[:3]) # affiche les trois premiers éléments
print(fruits[-3:]) # affiche les trois derniers éléments
print(fruits[2:4]) # affiche les éléments d'indice compris entre 2 (inclus) et 4 (exclu)
print(fruits[::2]) # affiche les éléments d'indice pair

En fait, le slicing s'écrit liste[start:end:step], avec exactement les mêmes arguments que la fonction range !

Autres opérations sur les listes

Pour connaitre la longueur d'une liste :

Python

Loading editor...

print(len(fruits))

Pour itérer sur les éléments d'une liste, c'est-à-dire parcourir tous les éléments un par un :

Python

Loading editor...

for fruit in fruits:
	print(fruit)

ou, alternativement :

Python

Loading editor...

for i in range(len(fruits)):
	print(fruits[i])

La première méthode parcourt directement les éléments de la liste un à un, tandis que la deuxième parcourt les indices de la liste (0, 1, 2, ...) et récupère les éléments avec leur indice.

Ajouter ou enlever des éléments

Pour ajouter un élément à la fin d'une liste, on utilise la méthode append.

Python

Loading editor...

fruits.append("Pêche")
print(fruits)

Une méthode est une fonction qui porte sur un objet, et elle s'utilise avec objet.methode(arguments...).

On peut aussi enlever un élément avec la méthode pop.

Python

Loading editor...

el = fruits.pop()
print(fruits)
print("L'élément enlevé est :", el)

Question 1

Essayez d'exécuter plusieurs fois le code ci-dessus et observez le résultat. Que se passe-t-il si on exécute le code une fois de trop ?

Par défaut, .pop() enlève le dernier élément de la liste. On peut lui passer un argument pour enlever un élément à un indice précis : fruits.pop(2) enlèvera l'élément d'indice 2.

On peut également additionner (concaténer) et "multiplier" des listes avec les opérateurs + et * :

Python

Loading editor...

fruits = ["Pomme", "Poire", "Fraise", "Tomate", "Abricot"]
fruits2 = ["Banane", "Kiwi"]
print(fruits + fruits2) # concaténation·

Python

Loading editor...

print(3 * fruits2) # répétition

Test d'appartenance

Pour tester si un élément est présent dans une liste, on utilise le mot-clé in :

Python

Loading editor...

fruits = ["Pomme", "Poire", "Fraise", "Tomate", "Abricot"]
if "Tomate" in fruits:
	print("La tomate est bien un fruit !")

Exercices : les nombres premiers

Comme toujours lorsque vous écrivez du code :

donnez à vos variables des noms explicites, en respectant la convention snake_case ;
commentez votre code lorsque c'est nécessaire ;
respectez les règles de présentation usuelles (espaces autour des opérateurs, etc).

Étude d'une liste prédéfinie

Un entier positif est dit premier si ses seuls diviseurs positifs sont et . Par exemple, est premier.

On vous donne ci-dessous la liste des nombres premiers entre 0 et 1000. Exécutez la cellule suivante afin de pouvoir utiliser cette liste dans la suite.

Python

Loading editor...

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]

Question 2

Répondez aux questions suivantes en vous aidant de code Python et de la liste fournie.

Combien y a-t-il de nombres premiers entre 0 et 1000 ?
Quels sont les 12ème, 33ème et 96ème nombres premiers ?
Affichez la liste des 20 premiers nombres premiers.

Python

Loading editor...

Question 3

Écrivez un code Python pour afficher tous les nombres premiers (entre 0 et 1000) de la forme , c'est-à-dire tels que est une puissance de 2.

Indice

Vous pouvez procéder dans le sens inverse : pour chaque puissance de 2 plus petite que 1000, regardez si est dans la liste nombres_premiers.

Python

Loading editor...

Construction de la liste des nombres premiers

Dans cette partie, on utilisera moins la liste nombres_premiers, et on va tenter de construire cette liste à l'aide d'un code Python.

Question 4

Écrivez une fonction est_premier qui prend en argument un entier et renvoie True si et seulement si il est premier.

Indice / Rappel

Un entier est premier s'il n'est divisible par aucun des entiers plus petits que lui (à part 1).
Si on a deux entiers n et d, n % d est le reste de la division euclidienne de n par d (aussi appelé "modulo" en informatique). Entre autres, cette quantité vaut 0 si et seulement si n est divisible par d.

Python

Loading editor...

Question 5

Testez votre fonction en vous assurant que les exemples suivants fonctionnent :

1 n'est pas premier
2 est premier
1024 n'est pas premier
42853 est premier
42857 n'est pas premier

Python

Loading editor...

Question 6

À l'aide de la fonction est_premier que vous avez réalisée, écrivez une fonction liste_premiers qui prend en argument un entier n et qui renvoie la liste des nombres premiers plus petits que n.

Vous pouvez tester votre fonction en comparant son résultat à la liste nombres_premiers de la première partie.

Python

Loading editor...

On peut afficher des courbes en Python à l'aide de la librairie matplotlib.pyplot. Il faut d'abord importer la librairie :

import matplotlib.pyplot as plt

Puis, pour afficher une courbe, on utilise les trois instructions suivantes :

plt.clf()
plt.plot(X, Y, "r-")
plt.show()

la première instruction efface les courbes qui auraient pu être tracées précédemment ;
la deuxième instruction crée la courbe elle-même. Elle prend en argument deux listes (ou tableaux) X et Y de même taille, ainsi qu'une chaîne de caractères indiquant la forme (par exemple "r-" pour une ligne rouge, ou "b+" pour des croix bleues) ;
la troisième instruction affiche le résultat.

Une expression parfois utile pour afficher des courbes est list(range(n)), qui construit la liste des entiers de 0 à n-1.

Question 7

Affichez la courbe des nombres premiers jusqu'à 10000 (où le n-ième nombre premier p est placé à la position (n, p)). Que remarquez-vous ?

Python

Loading editor...

Bonus : pour aller plus loin

Utiliser une simple fonction est_premier est une manière assez peu efficace de calculer la liste des nombres premiers. Les questions qui suivent vous proposent plusieurs optimisations possibles.

Question 8

Quelle est la taille maximale d'un diviseur d de n différent de n lui-même ? Déduisez-en une manière de tester un plus petit nombre de diviseurs dans une potentielle fonction est_premier.

Python

Loading editor...

Question 9

Est-il utile de tester les nombres pairs (supérieurs à 2) pour savoir s'ils sont premiers ?

En fait, tous les nombres premiers à partir de 5 sont de la forme ou , c'est-à-dire que n % 6 vaut 1 ou 5. En faisant une disjonction de cas en fonction de la valeur de n % 6, prouvez cette affirmation.

Python

Loading editor...

Question 10

Lorsqu'on calcule la liste des nombres premiers dans l'ordre croissant, on dispose, au moment de tester si n est premier, de la liste premiers des nombres premiers plus petits que n.

Que peut-on en déduire sur n si aucun élément de premiers ne divise n ?

Python

Loading editor...

Question 11

En combinant ces trois méthodes, écrivez une fonction liste_premiers_opt qui calcule efficacement la liste des nombres premiers entre 0 et n. Testez votre fonction en vous assurant qu'elle renvoie le même résultat que liste_premiers.

Python

Loading editor...

La fonction suivante mesure le temps d'exécution d'une fonction. Vous n'avez pas besoin de comprendre son code, simplement de l'exécuter. On l'utilise avec chrono(f, arg1, arg2, ...) avec f le nom de la fonction à chronométrer, et arg1, arg2, ... ses arguments.

Python

Loading editor...

import time
def chrono(f, *args):
    """
    Prend en argument une fonction f et ses arguments.
    Affiche le temps d'exécution de f, et renvoie sa valeur de retour.
    """
    before = time.time()
    ret_value = f(*args)
    total_time = time.time() - before
    print(f"La fonction s'est exécutée en {total_time} secondes.")
    return ret_value

Question 12

Utilisez la fonction chrono ci-dessus pour comparer les temps d'exécution des fonctions liste_premiers et liste_premiers_opt. Si vous le souhaitez, tracez une courbe du temps d'exécution des deux fonctions en fonction de n.

Python

Loading editor...

Entrez le code donné en cours pour accéder à la solution :

Code d'accès