PYTHON 2.7 Feuille d'exercice n°14 bis sur la division euclidienne
Cours:
• Soient a et b deux entiers naturels avec b non nul.
Considérons a ≥ b.
Nous voulons avoir le quotient et le reste de la division de a par b.
On peut procéder par soustraction.
On retranche à a l'entier b tant que la différence est positive.
On obtient ainsi le reste r de la division de a par b.
Le nombre de fois que l'on a soustrait b à a est le quotient q de la division de a par b.
• Notation :
Soient a et b deux entiers naturels avec b non nul.
Les affirmations suivantes sont équivalentes:
• • b | a
• • Il existe un entier q tel que a = b × q
• • b divise a
• • a est un multiple de b
• • Le reste de la division euclidienne de a par b est nul.
• • En Python2.7 cela s'écrit : a % b = 0
•NOMBRE PREMIER.
Soit a un entier naturel tel que a ≥ 2.
a est premier veut dire que seuls dans IN* 1 et a divisent a.
•COMMENT s'apercevoir qu'un entier a tel que a ≥ 2 est un nombre premier?
Soit a dans IN tel que a ≥ 2.
Première idée:
On connaît déja la liste des entiers naturels autres que 0 ou 1 ou 2 qui sont inférieurs
à l'entier a.
Si a est divisible par l'un d'eux c'est que a n'est pas premier
sinon c'est que a est premier
Seconde idée: ( Il y a un peu moins de travail )
On connaît déja la liste des nombres premiers qui sont inférieurs
à l'entier a.
Si a est divisible par l'un d'eux c'est que a n'est pas premier
sinon c'est que a est premier.
Troisième idée: ( Il y a encore moins de travail )
On connait la liste des nombres premiers inférieurs ou égaux à √a .
Si a est divisible par l'un d'eux c'est que a n'est pas premier
sinon c'est que a est premier.
----------------------------------------------------------------------------------------
EXERCICE 1:
Ecrire un programme avec while qui donne le reste et le quotient de la division
de l'entier naturel a parl'entier naturel non nul b.
-------------------------------------------------------------------------------------
REPONSE:
On peut proposer:
from random import*
def div():
a=input("Donner un entier naturel a : a = ")
b=input("Donner un entier naturel b non nul : b = ")
q=0
while b<=a:
a=a-b
q=q+1
print "Le quotient de la division de a par b est",q
print ("Le reste de la division de a par b est "),a
On obtient par exemple:
>>> div()
Donner un entier naturel a : a = 13
Donner un entier naturel b non nul : b = 2
Le quotient de la division de a par b est 6
Le reste de la division de a par b est 1
>>>
-------------------------------------------------------------------------
EXERCICE 2
Avec la première idée faire un script qui indique si un entier a
tel que a ≥ 2 est premier.
---------------------------------------------------------------------------------
REPONSE:
On peut considérer:
from random import*
def test_de_primalite():
a=input("Donner un entier naturel a tel que a>=2: a = ")
L=[]
for k in range( 2,a):
L.append(a%k)
if 0 in L:
print a,"n'est pas premier"
else:
print a," est premier"
On obtient par exemple:
>>> test_de_primalite()
Donner un entier naturel a tel que a>=2: a = 49
49 n'est pas premier
>>>
>>> test_de_primalite()
Donner un entier naturel a tel que a>=2: a = 13
13 est premier
>>>
------------------------------------------------------------------
EXECICE 3:
Donner un script qui pour déterminer si un entier naturel n tel que
2 ≤ n ≤ 10 000 est premier utilise le critère de primalité suivant :
<< Soit n un entier naturel tel que n ≥ 2.
Si aucun nombre premier p tel que p ≤ √n
ne divise n alors n est premier. >>
---------------------------------------------------------------------------
REPONSE:
On peut proposer le script suivant:
from random import*
def premier():
# voici la liste L1 des nombres premiers inférieurs au sens large à 100.
L1 =[ 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]
Lis=[]
L=[]
n = input("Donner un entier compris entre 2 et 10000 au sens large ")
g=n**0.5
for k in L1:
if k <=g:
Lis.append(k)
for i in range(len(Lis)):
L.append(n%Lis[i])
if 0 in L:
print n,"n'est pas premier"
else:
print n," est premier"
On obtient par exemple:
>>> premier()
Donner un entier compris entre 2 et 10000 au sens large 13
13 est premier
>>> premier()
Donner un entier compris entre 2 et 10000 au sens large 49
49 n'est pas premier
>>>
------------------------------------------------------------------------