Programmation - Factorisation de grands entiers
Le site UVa Online Judge regroupe des problèmes de plusieurs concours de programmation ouvert aux étudiants. Il propose de nombreux exercices de nature algorithmique dont la résolution se fait en écrivant un programme en C, C++ ou Java qui est ensuite vérifié automatiquement sur un ensemble de données test.
Pour illustrer certains points du cours, nous vous proposerons des problèmes issus de ce site. Après la création d'un compte, vous pourrez donc soumettre vos solutions au site UVa Online Judge puis envoyer à l'adresse vergnaud@di.ens.fr votre solution (ainsi qu'une courte justification théorique) lorsque celles-ci auront été acceptées.
Une introduction à la programmation en C peut être trouvée ici ou là.
Problème original : Factorizing Large Integers
Description
Étant donné un entier N inférieur à 10^16, donner sa décomposition en facteurs premiers.
L'entrée consiste en plusieurs cas à traiter. La première ligne contient le nombre T de cas à traiter (T ≤ 800). Les T lignes suivantes contiennent un entier N (1 < N ≤ 10^16).
La sortie consiste en la décomposition en facteurs premiers des T entiers (cf l'exemple pour le format de sortie)).
Exemple d'entrée
3 60 36 10007
Exemple de sortie
60 = 2^2 * 3 * 5 36 = 2^2 * 3^2 10007 = 10007
