Présentation du principe

Recherche entre 1 et un nombre entier quelconque des nombres premiers. Pour une borne supérieure à 100 000, il faudra faire preuve de patience.

Rappel:

• Nombres premiers = 1, 2, 3, 5, 7, 11, ...
• Un nombre premier est un entier divisible par 1 et par lui-même
  • ex: 6 n'est pas premier car 6=1*2*3
  • ex: 7 est premier car 7=1*7

Scripts à tester

Sur cette page quelques scripts vous sont présentés. Ne passez pas trop vite car ils (les scripts) sont une partie de la solution de l'exercice. Donc suivez ce conseil:

• Testez les scripts
• Comprenez les
• Et pourquoi pas commentez les avant de l'enregistrer...

Thème: Division euclidienne, reste, et quotient d'un entier quelconque

Premier script explicitant les diviseurs d'un nombre. Ici le nombre est nbre=24 (voir la deuxième ligne)

Script

#quete des nombres premiers
nbre=24
i=1
while i<=nbre:
	if nbre%i ==0:
		print (i,'est un diviseur de ',nbre)
		i=i+1
	else:
		i=i+1

Shell>>>

>>> %Run test.py
1 est un diviseur de 24
2 est un diviseur de 24
3 est un diviseur de 24
4 est un diviseur de 24
6 est un diviseur de 24
8 est un diviseur de 24
12 est un diviseur de 24
24 est un diviseur de 24

Idée suivante>>>

• Je suis en capacité de lister les diviseurs de 24 (ou de n'importe quel nombre)
• J'enregistre les diviseurs dans une liste
  • si ma liste ne contient plus de 2 éléments alors le nombre n'est pas premier
  • si ma liste contient 2 éléments alors le nombre est premier
    1 est un diviseur de 13
    13 est un diviseur de 13

Thème: Boucle Tant que et enregistrement dans une liste

Script

#quete des nombres premiers
nbre=13
i=1
list=[]
while i<=nbre:
    if nbre%i ==0:
        print (i,'est un diviseur de ',nbre)
        list.append(i)
        i=i+1
    else:
        i=i+1
print(list)

Shell>>>

>>> %Run essai.py
1 est un diviseur de  13
13 est un diviseur de  13
[1, 13]

Idée suivante>>>

• L'idée est de créer une seconde liste qui concatenera les nombres premiers au fur et à mesure
• La condition pour qu'un nombre rentre dans cette liste est que le nombre de ses diviseurs ne soit pas supérieur à 2
• Nécessite donc la création d'une grande boucle dans la boucle

Thème: Gestion d'une boucle dans une boucle

Script

#quete des nombres premiers
borne =100
premier=[1]
j=1
while j<=borne:
    nbre=j
    i=1
    list=[]

    while i<=nbre:
        if nbre%i ==0:
            print (i,'est un diviseur de ',nbre)
            list.append(i)
            i=i+1
        else:
            i=i+1
    print(list)
    if len(list)==2:
        premier.append(nbre)
    print (premier)
    j=j+1

Shell>>>

>>> %Run essai.py
1 est un diviseur de  1
[1]         << Liste des diviseurs du Nombre 1
[1]         << Liste des nbres premiers
1 est un diviseur de  2
2 est un diviseur de  2
[1, 2]      << Liste des diviseurs du Nombre 2
[1, 2]      << Liste des nbres premiers

-------
-------
-------
1 est un diviseur de  99
3 est un diviseur de  99
9 est un diviseur de  99
11 est un diviseur de  99
33 est un diviseur de  99
99 est un diviseur de  99
[1, 3, 9, 11, 33, 99]        << Liste des diviseurs du Nombre 99
[1, 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]     << Liste des nbres premiers jusqu'à 99
1 est un diviseur de  100
2 est un diviseur de  100
4 est un diviseur de  100
5 est un diviseur de  100
10 est un diviseur de  100
20 est un diviseur de  100
25 est un diviseur de  100
50 est un diviseur de  100
100 est un diviseur de  100
[1, 2, 4, 5, 10, 20, 25, 50, 100]       << Liste des diviseurs du Nombre 100
[1, 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]       << Liste des nbres premiers jusqu'à 100

La solution

Enfin, une des solutions possibles. Attention cependant à ne pas tricher, vous devez réfléchir avant de basculer sur cette page. Il n'est pas trop tard pour faire demi-tour... car  "L’apprentissage optimal est l’acquisition équilibrée de concepts, d’habiletés et d’une compétence métacognitive"

Vous noterez le input et le int de la seconde ligne, pour vous laisser le choix...

Script fonctionnel sans les impressions intermédiaires

#quete des nombres premiers
borne =int(input("Saisir un nombre entier, au dela de 10000 vous pouvez aller prendre un café ;)\nVotre saisie = "))
premier=[1]
j=1
while j<=borne:
    nbre=j
    i=1
    list=[]

    while i<=nbre:
        if nbre%i ==0:
            
            list.append(i)
            i=i+1
        else:
            i=i+1
   
    if len(list)==2:
        premier.append(nbre)
    
    j=j+1
print (premier)

Shell>>>

>>> %Run essai.py
Saisir un nombre entier, au dela de 10000 vous pouvez aller prendre un café ;)
Votre saisie = 1000
[1, 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]