Algorithmes mathématiquesBeginner

Algorithme d'Euclide (PGCD)

Algorithme ancien d'environ 300 av. J.-C. qui calcule efficacement le plus grand commun diviseur de deux entiers. Basé sur le principe que PGCD(a, b) = PGCD(b, a mod b). L'un des plus anciens algorithmes en usage continu, formant la base de la théorie des nombres, de la cryptographie et de la simplification des fractions.

#mathematical#number-theory#ancient-algorithm#gcd-lcm

Complexity Analysis

Time (Average)

O(log min(a, b))

Expected case performance

Space

O(1)

Memory requirements

Time (Best)

O(log min(a, b))

Best case performance

Time (Worst)

O(log min(a, b))

Worst case performance

Input Numbers (positive integers)

Number A

Number B

Quick Presets:

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in Algorithmes mathématiques

Crible d'Ératosthène

Beginner

Trouvez tous les nombres premiers jusqu'à n en marquant itérativement les composites. Nommé d'après Ératosthène de Cyrène (vers 276-194 av. J.-C.).

O(n log log n)

O(n)

mathematicalprime-numbers

Start Learning

Triangle de Pascal

Beginner

Tableau triangulaire de coefficients binomiaux où chaque nombre est la somme des deux nombres directement au-dessus. Nommé d'après Blaise Pascal (1623-1662), bien que connu des mathématiciens des siècles plus tôt. Démontre de beaux motifs mathématiques incluant l'expansion binomiale, la combinatoire et les connexions aux nombres de Fibonacci.

O(n²)

mathematicalcombinatorics

Start Learning

Algorithme d'Euclide étendu

Intermediate

Étend l'algorithme d'Euclide pour trouver les entiers x et y satisfaisant l'identité de Bézout : ax + by = PGCD(a, b). Non seulement calcule le PGCD mais trouve aussi les coefficients des combinaisons linéaires. Fondamental pour l'arithmétique modulaire, la cryptographie RSA et la résolution d'équations diophantiennes linéaires.

O(log min(a, b))

O(1)

mathematicalnumber-theory

Start Learning

Back to Algorithmes mathématiques