Durée : 2h. Notes de cours personnelles (manuscrites ou polys et sorties imprimante), TD et TP autorisés. Calculatrices autorisées. Autres documents (dont livres) interdits. Calculatrices autorisées.
De nombreux algorithmes nécessitent des suite de nombres premier. Dans les transmissions de données par exemple, il est aujourd'hui important d'empêcher la lecture des informations par toute personne capable d'intercepter le message. Il faut donc coder l'information. Les méthodes utilisées nécessitent des clefs (publiques et privées) qui sont des nombres qui doivent être premiers entre eux. Nous nous limiterons par exemple dans la question 3 à des nombres entiers entre 0 et 1023 (donc sur 10 bits, par rapports aux clefs qui peuvent faire 128 bits)), et les calculs que nous effectuerons ici ne pourraient pas s'appliquer aux clés réelles, car ils nécessiteraient des moyens de calculs phénoménaux (c'est d'ailleurs fait exprès).
Ecrivez en Fortran un programme qui demande deux entiers et dit si l'un est multiple de l'autre. Vous utiliserez obligatoirement l'algorithme suivant :
Si vous écrivez une fonction retournant le reste de la division de ses deux arguments, elle vous servira ici et vous pourrez la réutiliser dans la suite du sujet, mais ce n'est pas obligatoire.
Pour vérifier si deux nombres sont premiers entre eux (c'est à dire qu'aucun nombre autre que 1 ne les divise), nous allons rechercher leur PGCD (plus grand commun diviseur) qui doit valoir 1 pour qu'ils soient premiers entre eux. Nous allons utiliser l'algorithme d'Euclide :
Pour trouver le PGCD de deux entiers A1 et A2, on calcule A3 qui est le reste de A1/A2. Puis on calcule A4 qui est le reste de A2/A3, A5 qui est le reste de A3/A4, etc... jusqu'à ce que le reste soit nul. Le reste précédent (le dernier non nul) est le PGCD de A1 et A2.
Ecrivez en Fortran un programme qui demande deux entiers et dit si s'ils sont premiers entre eux. Vous utiliserez obligatoirement l'algorithme d'Euclide. Si vous le pouvez, vous découperez votre programme en plusieurs fonctions. Remarque : il n'est pas nécessaire de mémoriser tous les calculs intermédiaires de l'algorithme d'Euclide, seul le dernier et l'avant dernier.
On désire déterminer tous les nombres premiers entre 1 et 1023 compris. Pour cela on prépare un tableau T allant jusqu'à T(1023). En fin de programme il faudra que T(i) vaille 1 si i est premier, 0 sinon. Pour commencer, on élimine tous les nombres pairs (en mettant 0 dans une case sur deux de T) et on met T à 1 pour les nombres impairs. Puis pour i allant de 3 à la racine de 1024 (il est inutile d'aller jusqu'à 1024, mais vous n'avez pas besoin de comprendre pourquoi), s'il n'a pas encore été éliminé (s'il est encore défini comme premier, T(i)=1), on le laisse tel quel mais on élimine tous ses multiples (T(multiple)=0). Votre programme affichera tous les nombre premiers trouvés. Il est interdit d'utiliser un autre algorithme. La décomposition judicieuse en quelques fonctions sera appréciée, mais n'est pas obligatoire. La limite 1024 sera définie par un "parameter".
que fait ce sous-programme (globalement, pas ligne par ligne) ?
subroutine ttt(tab1,nb1,tab2,nb2,tab3,nb3)
implicit none
integer nb1,nb2,nb3
real tab1(*),tab2(*),tab3(*)
integer i
real x
if(nb1.lt.1) then
print *,'fatal error'
stop
endif
x=tab1(1)
do 10 i=2,nb1
x=x+tab1(i)
10 continue
x=x/nb1
nb2=0
nb3=0
do 20 i=1,nb1
if(tab1(i).gt.x) then
nb3=nb3+1
tab3(nb3)=tab1(i)
else
nb2=nb2+1
tab2(nb2)=tab1(i)
endif
20 continue
end subroutine ttt
Remarques : Si le sujet n'est pas assez précis dans certains cas, faites l'hypothèse que vous préférez, mais n'oubliez pas d'expliciter vos suppositions sur la copie. Si vous n'arrivez pas à retrouver la syntaxe exacte d'une fonctionnalité du Fortran, expliquez en français ce que vous voulez faire. Les questions qui rapportent le plus de points sont bien évidement la 2 et la 3.
pour retourner au sommaire des sujets d'examen, cliquez ici
Si vous le désirez, vous pouvez regarder ici une proposition de réponses.
Patrick TRAU, ULP - IPST fev 03