Discussion :

[salomee2510]

Bonjour, je suis étudiante et j'ai un dm de math sur lequel je galère vraiment.
Il faut que je crée un algorithme sur python qui permet de générer n couples de nombres entiers compris entre 1 et 1 000 000 000 et qui calcule la proportion de couples premiers entre eux.
Voila merci pour votre aide.

[Flodelarab]

Bonjour

Qu'as-tu déjà fait ?
Quelle est la difficulté ?

À ta place, je tirerais n entiers entre 1 et 1 000 000 000, puis calculerais la décomposition en facteurs communs de chacun.
Et les nombres qui n'ont pas de facteurs communs forment un couple d'entiers premiers entre eux.

[salomee2510]

Alors j'ai réussi à ce que python puisse générer deux nombres à et b au hasard seulement je ne sais pas comment traduire sur python qu'il faut qu'il fasse n fois cela. Je suis en seconde générale.

[Flodelarab]

Fais une boucle.

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for i in range(n):
    code()

[wiwaxia]

Bonjour,

Le dénombrement des couples d'entiers (a, b) premiers entre eux peut effectivement résulter d'une boucle simple, par un ensemble d'instructions apparentées à celles-ci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
CONST Nmax = 1000000000; Nc = 10000;
VAR a, b, k, m, Np: LongInt; r: Reel;
 
Np:= 0; Randomize;
FOR k:= 1 TO Nc DO 
  BEGIN
    m:= Random(Nmax); a:= m + 1;
    m:= Random(Nmax); b:= m + 1;   
    IF TestP(a, b) THEN Inc(Np)
  END;
r:= Np / Nc;          // Rapport du nombre de couples d'entiers premiers entre eux au nombre total

la fonction booléenne TestP(i, j) correspondant à un plus grand commun diviseur égal à l'unité:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
FUNCTION TestP(i, j: LongInt): Boolean;
  BEGIN
    TestP:= (Pgcd(i, j)=1)
  END;

Il est sans doute possible d'accélérer l'exécution du programme en contournant le calcul du PGCD dans quelques cas évidents et relativement fréquents, par exemple par les instructions:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
FUNCTION TestP(i, j: LongInt): Boolean;
  VAR Test, Test2, Test3: Boolean;
  BEGIN
    Test2:= ((i MOD 2 = 0) AND (j MOD 2=0));
    Test3:= ((i MOD 3 = 0) AND (j MOD 3=0));
    IF (Test2 OR Test3) THEN Test:= False
                        ELSE IF (Pgcd(i, j)>1) THEN Test:= False
                                               ELSE Test:= True; 
    TestP:= Test
  END;